시간복잡도

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

 

이런 시간복잡도를 가지고 있다. 시간복잡도는 간단하게 한 input이 output으로 나오는 시간이라고 생각하면 된다.

예를 들어,

for(int i = 0; i < n; i++)
	for(int j = 0; j < n; j++)
    	int sum += temp[i][j]
        
// 결과는 O(n^2)

알고리즘을 풀 땐 1초에 1억번의 연산이 가능하다고 생각하면 편하다.

 

만약 입력이 10,000이다.

만약 2중 for문을 쓴다고 하면  일만 * 일만 = 100,000,000 총 1억의 시간복잡도를 갖게 된다.

보통 백준같은 코딩 사이트에선 제한시간이 1초이니 이중 반복문을 사용할 때 가능한 건 입력이 10,000 미만이 되겠다.