[알고리즘] 시간복잡도

위로 갈수록 알고리즘이 매우 빨라지며 아래로 갈수록 nn의 값이 커지고 급격하게 알고리즘의 수행 시간이 증가합니다. 위의 표를 보시면 대충 아시겠지만 대략 컴퓨터가 1억 번의 연산을 하기 위해서는 1초 정도의 시간이 필요합니다.

 

만약 1만개의

입력데이터가 들어온다면 O(n)의 경우에는 0.1초 O(n²)의 경우 1만 * 1만 = 1억이므로 대략 1초정도의 시간이 필요하겠습니다.

 

만약 1억 개의 데이터가 들어오는데 실행시간이 1초인 알고리즘 문제를 풀려면 무조건 O(n)이나 O(Log N)의 시간 복잡도로 문제를 풀어야 한다는 이야기겠죠?

 

즉, 제한시간이 1초인 문제에서 입력데이터가 10,000개가 넘는 경우에 이중 for문을 사용하면 시간초과발생

 

제한시간과 입력데이터에 따라 문제 푸는 방향을 정해야 한다.