알고리즘 - O(log N) ...

ITWeb/개발일반 2012. 5. 10. 13:36

알고 쓰면 약, 모르고 쓰면 허풍 ㅋㅋ

[원본링크]

[원본글]

평균과 최악의 경우 분석


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

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

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

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

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

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

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

O(n!) : 입력 자료의 크기가 N일경우 n*(n-1)*(n-2)... * 1(n!) 번만큼의 수행시간을 가진다. ex)외판원 문제(TSP)의 기본적인 해법


: