[30일코딩] Running Time and Complexity

Day25. Running Time and Complexity 튜토리얼에서는

공학의 가치 중 하나인 "효율성"과 효율적으로 구현하는 방법을 소개해주었다. 

이전에 보고서를 배치잡으로 생성할 때

1) 알고리즘, 2) DB 설계 3) DB 인덱스 설정에 따라

작업의 속도가 천지차이라는 것을 느낄 수 있었는데...

그런 대단한 개념을 비교적 쉬운 코드로 설명, 예제로 구현해볼 수 있다는 점에

또 한번 감탄했다 ㅠ_ㅠ (정말 강추강추)

컴퓨터 메모리 vs. 응답시간

Space - time Trade off

자원이 한정되어 있기 때문에 "효율성"은 매우 중요하다.

자원의 두 축은 컴퓨터 메모리와 시간이다. 

컴퓨터 자원이 과거대비 매우 커졌기 때문에- available

사람들의 응답속도에 대한 기대감이 커졌기 때문에-

현재는 응답시간이 조금 더 우선되는 가치처럼 여겨진다.

하지만 실질적으로는

내 상황과 각 작업에 기대하는 사용성에 따라 다르다.

코드 리드타임

Day 25에서는 알고리즘(코드)의 리드타임을 산정하는 방법을 보여준다.

How fast is a given function

based on a given input of size N

dataSize N 이라고 가정했을 때,

Case1. For Loop, 로직 에 대한 리드타임

i = 0 선언, 할당                       1 번

i < s.length() 0~n                   n+1 번

i++  0~n-1                              n 번

if 조건문 확인                          n 번

sum++                                    n 번

>> n번이니까 linear (일차함수)

Case2-1. Nested For  Loop 에 대한 리드타임 

Outer For Loop n 번, Inner For Loop m 번 가정했을 때

 

1) int j=0 는 i=0~n-1 일때 까지이니 n 번

2) j < c.length; 는 n*m

- i= 0 일 때 j도 m번

- i 가 n-1 때까지 n번 실행

3) Inner Loop 로직도 각각 n*m 번

>> n * m  해서 Multiplicable(n*m) or Quadric(이차함수) 

Case 2-2. 그 외 Collection 자료구조를 통한 코드 리드타임

HashMap 에 String 의 Char 를 Key 로 등록하고

각 Char 에 대하여 카운트를 한다.

1) 1st For Loop 로직이

s의 글자수만큼 동작, 따라서 n번

2) 2st For Loop 로직이 

HashMap의 Key 만큼 (중복 제거, n보다 작음) 동작

따라서 max n번

>> 2*n Linear (일차함수) 로 변경

Case 2. 대비 자원 활용, 시간 단축!!! 

리드타임 산정방식

위의 방식을 함수로 정리해보면 다음과 같다.

사용된 로직 중 가장 dominant 리드타임을 가지는 방식이

해당 로직의 리드타임 방식이다.

[리드타임 산정방식]

1) O(1) : constant 상수

2) O(logN): 로그함수   

3) O(n): 일차함수    Linear

4) O(n^2): 이차함수 Quadric

Task: Prime Number

이렇게 break-down code 하는 강의 설명이 끝나고- Task!!!

Task 는 숫자에 대해 서수 (Prime Number) 여부를 확인해야 했다.

For Loop 로직 외에도, 논리적으로 불필요한 부분을 줄임으로써 리드타임을 줄일 수도 있다. 

There are a number of optimizations you can perform.

Get started on today's challenge! And, when you're done,
be sure to check the Editorial for a comparison of four primality algorithms.

Case 1. 일반적으로 1, 자신 외의 모든 수로 나누어서

나머지가 떨어지지 않는지를 확인한다. 

Case 2. 그런데 이걸 square root 제곱근까지만 진행해도 된다.

제곱근 이후에는 2, 50 ~ 50, 2 똑같은 쌍이 순서만 바뀌기 때문.

이렇게 1번 케이스보다 1/2 의 작업만 하면 된다.

정리

효율성, 그 중에서도 리드타임!

리드타임을 줄이기 위한 방법으로 이런것들을 배웠다.

- Collection 활용

- 논리구조 활용

- break 문

- etc.

코드를 작성할 수록 경험치가 쌓일 것 같다 :) (뿌듯)

특히 Collection 을 잘 활용하는 방법을 배우기 위해서라도

꼭 자료구조론을 공부하고 싶다. (불끈!)