알고리즘 시간복잡도 Big-O

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록

(주요 알고리즘 배울 때마다 슈퍼마리오 블로그 정독할 것!)

 

 

 

[강의 주요 내용]

• 알고리즘의 수행시간을 함수로 표현
• 다항식의 성질에 따라서 수행시간이 어떻게 변화하는가
• 수행시간을 표기하는 간단한 방법

 

저번 시간에 계산한 기본연산 수행시간 (3번은 중간에 -가 아니라 +임)

함수로 표현하여 그래프를 그림. 

1. Algorithm2가 Algorithm1보다 2배 느리다. True
2. Algorithm3 n<5/3면 Algorithm2보다 빠르다. 모든 n에 대해서 Alrogithm1보다는 느리다.
3. Algorithm3는 n>5/3면 항상 Algorithm2보다 느리다. 

T1(n), T2(n), T3(n)

앞의 두 개는 n값에 따라 선형적으로 증가하는 반면, T3(n)은 제곱으로 증가함. (최고차항이 n제곱)

 

n이 증가함에 따라 얼마만큼 빠른 속도로 기본연산 횟수가 증가하는가는 최고차항이 결정함.

 

모든 함수를 다 분석해서 표현하기보다는 최고차항만 표시하면 수행시간의 대략적인 형태 파악 가능. -> Big-O 표기법

 

Big-O 표기법

1. 최고차항만 남긴다
2. 최고차항 계수(상수)는 생략한다
3. Big-O로 감싼다

T1(n) = 2n-1
T1(n) = O(n)  최고차항만 표기

T1(n)과 T2(n)의 수행시간은 구체적인 관점에서는 2배 차이가 남.

하지만 증가율의 관점에서 봤을 때 이는 크게 중요하지 않다.

그렇기에 BigO 표기법에 따르면 두 알고리즘은 같은 수행시간을 가짐.

 

 

예제

1.

def increment-one(a):
	return a + 1

T(n) = 1, O(1) = O(n0)

 

2.

def number-of-bits(n):
	count = 0
    while n > 0:
    	n = n // 2
        count += 1
      return count

계산하면 T(n) = C*log2n + 1, Big-O로 표기하면 T(n) = O(log2n)

 

집합관계로 표현

 

 

여름방학에 구름 열어주시면 과제 해볼 것!