시간 복잡도

시간복잡도?

문제 해결시 걸리는 시간(연산).

• 수행 시간 : 시간 복잡도 (CPU)
• 메모리 사용량 : 공간 복잡도 (RAM)

http://blog.naver.com/loudon23

• logN:입력N에 따라 log로 실행시간이 늘어남, 동적 프로그래밍처럼 큰문제를 작게쪼갤 때 나타남
• N(Linear) :입력N에 선형적으로 실행시간이 늘어남
• N logN: logN상태에서 다시 하나로 모음
• N^2:이중 loop
• N^3:삼중 loop
• 2^n:입력값N에 따라 실생시간 급격하게 증가 

O(N)

• Big-O(빅-오 표기법) : O(N) 알고리즘 실행시간의 상한을 나타낸 표기법(최악의 경우)
• Ω(오메가)표기법 : Ω(N) 알고리즘 실행시간의 하한을 나타낸 표기법 (최상의 경우)
• Θ(세타)표기법 : Θ(N) 알고리즘 실행시간의 평균시간을 나타낸 표기법(평균의 경우)