시간복잡도 이용하여 코드 짜기

시간복잡도란?

프로그램의 수행 시간을 수식으로 나타낸 것

 

 

표현법

Big-O Notation
★결국 사용하는 표현법
적어도 n에 비례하는 시간 ≒ 아무리 느려도 n에 비례하는 시간
"우리 아이는 아무리 못해도 전교 5등까지 했어요"

Big-Omega Notation
최소한 n에 비례하는 시간 ≒ 아무리 빨라도 n에 비레하는 시간
"우리 아이는 전교 5등까지 해봤어요"
→위험 부담 발생 → 사용 X

Big-Theta Notation 빅 O + 오메가
정확히 n에 비례하는 시간 ≒ 어떠한 경우에도 n에 비례하는 시간
→코드가 얼마나 돌아갈지 정확히 알기 어려울 경우 → 사용 X

 

 

 

시간복잡도 계산하기

O(1)

printf(sth);              		//#1
a+b;					  //#2
a*b;					  	//#3
if(a==b){}				  //#4

＝n에 비례하지 않는다
＝입력의 크기에 관계없이 일정한 시간이 소요된다

 

 

반복문의 시간 복잡도

O(1)

for(i=1; i<=10억; i++){
	print(i);
 }

☞10억은 입력값에 따라 변하지 않고 고정이 되어 있음

☞=n에 비례하지 않는다=O(1)

☞'상수 몇 번'이 중요하지 않다→가장 영향력 있는 항만을 남긴다

 

 

 

O(n)

for(i=1; i<=n; i++){
	print(i);
 }

O(1)×n = O(n)

for(i=1; i<=n+1; i++){
	print(i);
 }

※가장 영향력 있는 항만을 남긴다.

O(1)×(n+1) = O(n+1) ······································································(  X )

O(1)×(n+1) = O(n) ············································································( ○ )

 

 

 

O(n²)

for(i=1; i<=n; i++)
	for(j=i+1; j<=n; j++)
    		print(i+j);

결론: 이중 for문의 시간복잡도는 O(n²)

O(1)×(n-i)×n = O(n(n-i)) ······································································(  X )

☞i가 뭔지 알 수 없음

☞print가 몇 번 불리는지 계산하기

 

i=1	(n-1)번	▶
i=2	(n-2)번
…	…
i=n	(n-n)번

···············( ○ )

 

 

 

cf. 퀵 정렬을 이중 for문보다 효율적인 이유?

이중 for 정렬	O(n²)
퀵 정렬