알고리즘 시간 복잡도 계산

알고리즘 문제에서 시간제한이 있다. 시간제한에 대해 자신의 코드가 최악의 경우에 몇 초정도 나오는지 시간함수를 통해

정확히 알아낼 수도 있지만 대략 짐작을 빠르게 할 수 있다. 

시간 복잡도 표기법에는 3개가 있다.

빅오 표기법 : 알고리즘 실행시간의 상한

오메가 표기법 : 알고리즘 실행시간의 하한

세타 표기법 : 알고리즘 실행시간의 평균시간

먼저, 자신의 코드의 시간복잡도 빅오를 계산한다. 대부분의 코드가 n제곱이거나 n로그n인 경우가 많다.

그 후 문제의 제한 범위를 고려하여 입력이 몇개 들어가는지 고려한다.

대략, n삼승의 알고리즘은 2560의 입력까지 1초 안에 풀 수 있다.

n제곱의 알고리즘은 40960의 입력까지 1초 안에 풀 수 있다.

n로그n의 알고리즘은 20,000,000의 입력까지 1초 안에 풀 수 있다.

n의 알고리즘은 1억6천만 입력까지 1초 안에 풀 수 있다.

위의 경우에서 조건문이나 다른 연산이 포함되면 그런 경우도 고려하여 대략 자신의 알고리즘의 시간 계산을 할 수 있다.

아래의 사이트에서 좀 더 자세히 공부할 수 있다.

참고 : http://book.algospot.com/estimation.html

작성자 : 히더