[시간복잡도] 점근적 표기법과 시간복잡도 개념

 

점근적 표기법

점근적 표기법에는 크게 O, Ω, Θ 각 빅-오, 빅-오메가, 빅-세타라고 부릅니다.

 

다음 다항식을 점근적 표기법으로 분류해보겠습니다.

 

예시 다항식 : n^3+n^2+n−1 

• O(빅-오)에서는 가장 높은 차수보다 같거나 높은 식을 뜻합니다. 
  • O(n^3), O (n^6) O(n^100) 모두 표현 가능하지만, 타이트하게  O(n^3)으로 라고 결정합니다.
• Ω(빅-오메가) 가장 높은 차수보다 같거나 낮은 식을 뜻합니다.
  • Ω(n^3), Ω(n), Ω(logn) 모두 표현할수 있습니다.
• Θ(빅-세타) 는 최고차항을 뜻합니다.
  • 가장 높은 차수는 n3 이므로 Θ(n3)이 됩니다.

 

 

대입과 조건문의 시간복잡도

코드의 실행 횟수를 점근적 표기법으로 추상적으로 표현할 수 있는데 이것을 시간복잡도라고 부릅니다.

 

set a = 5 // O(1)
if a != 10 // O(1)
	print('hello') // O(1)

 

상기 코드의 시간 복잡도를 계산해보면 다음과 같습니다. print 메서드를 O(1)로 가정한다면, 대입(set a= 5)도 O(1)이고, print 도 O(1)입니다. if a !=10 도 단순히 한번 두 값을 비교연산을 수행하기에 O(1)입니다.

따라서 상기 코드의 시간복잡도는 O(1) 입니다.

 

참고사항

for loop를 1억번(100,000,000) 도는데 걸리는 시간은 약 1초입니다. 

 

제한 시간이 1초인 경우에 구현할 코드의 시간복잡도를 O로 계산했다고 가정하면,

N의 범위에 따라 제한 시간안에 처리할 수 있는지 파악할 수 있습니다.

 

 

N의 범위	수행 가능한 시간복잡도	계산식
N≤10	O(N!), O(2^N), O(3^N)	10!                               = 3,628,800 2^10                            = 1,024 3^10                            = 59,049
N≤20	O(2^N)	2^20                            = 1,048,576
N≤100	O(N^4)	100^4                          = 100,000,000
N≤500	O(N^3)	500^3                          = 125,000,000
N≤1,000	O(N^2), O(N^2 * logN)	1000^2                        = 1,000,000 1000^2 * log1000        = 1,000,000
N≤100,000	O(N), O(NlogN), O(logN), O(1)	100,000 * log100,000 = 500,000 log100,000                  = 5