시간복잡도 Big-O 표기

- 시간복잡도를 표기함으로써 작성한 코드가 얼마나 시간이 소요될지 알 수 있다.

 

Big-O 표기법

O(1)	O(log n)	O(n)	O(n log n)	O(n^2)	O(n^3)	O(2^n)
상수 시간	로그 시간	직선적 시간	로그 직선적 시간	2차 시간	3차 시간	지수 시간
Better <---> Worse

 

시간복잡도를 분석하는 것은 input n에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것과 같다. 그리고 이는 Big-O 표기를 이용하여 정의할 수 있다.

 

1. O(1)

int sum = N * (N + 10) / 2;

2. O(N)

int sum = 0;
for (int num = 1; num <= N; num++) {
	sum += num;
}

3. O(n^2)

int sum = 0;
for (int num = 1; num <= N; num++) {
	for (int num2 = 1; num2 <= N; num2++) {
    	if(num == num2) {
        	sum += num;
        }
    }
}