[알고리즘 기초] 시간복잡도

알고리즘의 시간복잡도

입력의 크기가 커질때 시간이 어떤 속도로 증가하는 지 나타냄

시간 복잡도는 O()으로 표기

 

 

1) 규칙

입력의 크기 : n

ex: 입력이 정수 배열일 때 n은 배열의 크기를 나타낸다 / 입력이 문자열일 때 n은 문자열의 길이를 나타낸다

 

O(1)

코드가 단일 명령어로만 구성되어 있을 때 (ex: a += 1)

 

O(n)

반복문 안의 내용이 n번 수행될 때

for i in 0...count {
	//......
}

O(n²)

이중반복문

for i in 0...count {
	for j in 0...count {
    	//.....
    }
}

 

TIP !
코드에서 시간복잡도가 다양하게 구성되어 있을 때는 가장 큰 것이 적용된다.
어차피 가장 느린 것이 있으면 느리기 때문이다.

 

TIP !
sort() = O(nlog n) 

 

2) 순서

O(1) -> O(log n) -> O(루트n) -> O(n) -> O(nlog n) -> 0(n제곱) -> O(n세제곱) -> 0(2n승) -> O(n!)

 

 

3) 효율성

대부분의 문제의 시간제한이 1초라고 하면 1초는 대충 어림잡아 1억(=10⁹)정도이다.

만약 입력의 크기가 n=10⁵고, 시간복잡도가 O(n²)이라고 하면 약 (10⁵)²=10¹⁰번의 연산을 하기에 시간초과가 날 것이다.

그렇기에 O(n2)보다 작은 시간복잡도를 선택하여 연산을 수행해야한다

입력의 크기	시간 복잡도 선택
n <= 10	O(n!)
n <= 20	O(2n)
n <= 500	O(n3)
n <= 5000	O(n2)
n <= 106 (1,000,000=백만)	O(nlog n) 이나 O(n)
n >>>>>> 클 때	O(1) 이나 O(log n)