Big O notation

 

동작하는 프로그램의 효율성을 왜 재야할까?

큰 데이터를 분석할 때, runtime이 너무 오래 걸리면 결국 효용성이 없는 프로그램이라는 뜻!(indfficient)

 

program 의 효율성을 따질 때 고려할 것

-Algorithm : (1)문제를 풀기 위하여 (2)명확히 정의된 지시들

- Data Structure : 데이터가 만들어져 있는 구조

모두 중요하다!!

 

Big O notation

왜 우리는 효용성을 고려할 때, Big O notation을 사용할까?

Big O notation은 최악의 경우를 가정하여 runtime이 '적어도' 이정도는 걸릴 것이다 라는 보장을 한다.

--> 현업에서는 적어도 얼마나 걸릴지가 중요하기 때문에 Big O notation을 주로 사용함.

 

Big O notation이란,

f(N) = O(g(N)) 이때, f(N) <= c * g(N) 이고 N >=n0 이다.

 

g(N) 이란? : Growth rate 증가율

C^N > N^k > N^2 > NlogN > N > logN > C

 

T1(N) = O( f(N) )  ,  T2(N) = O( g(N) )

T1(N) + T2(N) = max( O( f(N) )  , O( g(N) ) )   # 두 알고리즘을 연달아 실행함

T1(N) * T2(N) = O( f(N) * g(N) )                         # 반복문 속의 반복문

 

Algorithm Analysis

프로그램을 짤 때, 최대 몇 시간이나 걸릴지 수학적으로 계산이 가능하다.

 

프로그램의 line 마다 iteration이 몇 번 도는지 계산하면 됨~

 

예를 들어 다음과 같은 함수가 있다고 가정하자...

def calculateIntegerRangeSum(intFrom, intTo) :

	intSum = 0                                   # 1 line     
    
    for itr in range( intFrom, intTo) :          # 2 line
    	intSum = intSum + itr                    # 3 line
        
    return intSum                                #4 line

(0) 함수 내에 line 별로 연산 수를 계산한다.

 

(1) 1 번째 줄에서는 변하는 것이 없음. 따라서 1 iteration

(2) 2 번째 줄에서는 itr이 변한다! 몇 번이나 변하냐면 range( intFrom, intTo )로 만들어진 list 길이만큼 N iteration

(3) 3 번째 줄에서는 intSum 이 변한다. 몇 번이나 변하냐면 (2)에서 만들어진 리스트만큼 -> N iteration

(4) 4번째 줄에서는 변하는 것이 없음. 따라서 1 iteration

 

(5) 총 몇 번을 iteration 했느냐면 2N + 2 iteration!

 

(6) O(N)