Big-O 표기법

함수 값을 결정하는 최고차항만으로 간단하게 표기

알고리즘의 수행시간 : 최악의 경우의 입력에 대한 기본연산 횟수

• Algorithm 1 : T(n)=2n-1
• Algorithm 2 : T(n)=4n-1
• Algorithm 3 : T(n)=n(n-1)/2*3+1

알고리즘 시간복잡도 글 참고

Algorithm 1은 Algorithm 2보다 2배 빠르다.
Algorithm 3은 n<5/3 일 때 Algorithm 2보다 빠르고 모든 n에 대해서 Algorithm 1보다 느리다

Algorithm 1과 Algorithm 2는 n에 대해 선형적으로 증가한다.(최고차항 n)
->n에 대하여 정비례하게 증가

Algorithm 3은 제곱으로 증가한다.(최고차항 n2)
->n에 대하여 기하급수적으로 증가

• Algorithm 1 : T(n)=2n-1 -> O(n)
• Algorithm 2 : T(n)=4n-1 -> O(n)
• Algorithm 3 : T(n)=n(n-1)/2*3+1 -> O(n2)

1. 최고차항만 남긴다
2. 최고차항 계수는 생략한다.
3. Big-O

T(n)=1

def increment_one(a):
	return a+1 #상수 

O(n0)=O(1)

def number_of_bits(n):
	count=0
    while n>0:
    	n=n//2
        count += 1
    return count

O(log2n)