Running Time

• 일반으로 input size가 커질 수록 running time이 증가
• Average case time을 내기 어려움

Experimental Studies(실험적 측정법)

• 실험적으로 알고리즘의 성능을 조사
  

from time import time
start_time = time()
run algorithm
end_time = time()
elapsed = end_time - start_time

Limitiations of Experiments

• 실험적 측정법의 한계
  : Difficult
  : 즉, 알고리즘이 맞는지 틀린지도 알지 못한 채 일단 '만들어야'하기 때문에 그렇게 좋은 방법은 아님

Pseudocode

• High-level description of an algorithm

Worst Case Execution Time

worst case에 중점을 두고 running time 계산

Seven Important Functions

Comparision of Two Algorithms

Constant Factors

• 상수 무시
  

Counting Primitive Operations

def find_max(data):
	biggest = data[0]
    for val in data:
    	if val > biggest
        	biggest = val
    return biggest 

Big Oh Notation

Computing Prefix Averages

• 누적 평균
  

Prefix Averages(Quadratic)

def prefix_average1(S):
	n = len(S)
    A = [0] * n
    for i in range(j+1):
    	total += S[i]
        A[j] = total / (j+1)
    return A

Algorithm prefixAverage1 runs in O(n2)

Prefix Averages2(Looks Better)

Algorithm prefixAverage2 still runs in O(n2)

Prefix Averages3(Linear Time)

Algorithm prefixAverage3 runs in O(n)

Relatives of Big Oh

Big Omega

Big Theta

Intuition for Asymptotic Notation

Example Uses of the Relatives of Big Oh