알고리즘 복잡도

• 알고리즘
• 계산 복잡도 이론(Computational complexity theory)
• What does O(log n) mean exactly?
  

복잡도

O(1)

입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘

O(log N)

입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다.

O(N)

입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다.

O(N log N)

입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가진다.

O(_N2)

입력 자료의 크기가 N일경우 N^2 번만큼의 수행시간을 가진다.

O(_N3)

입력 자료의 크기가 N일경우 N^3 번만큼의 수행시간을 가진다.

O(₂n),

입력 자료의 크기가 N일경우 2^N 번만큼의 수행시간을 가진다.

O(n!)

입력 자료의 크기가 N일경우 n*(n-1)*(n-2)... * 1(n!) 번만큼의 수행시간을 가진다. 일반적인 알고리즘 문제의 기본 해법은 대부분 이 수행시간을 가진다.ex)외판원 문제(TSP)의 기본적인 해법