time complexity
-
시간복잡도(Time Complexity) 정리algorithm 2013. 4. 18. 11:36
Time Complexity알고리즘의 시간복잡도(Time Complexity)란 함수가 입력된 값을 처리하는데 걸리는 시간을 측정한 값을 의미함.일반적으로 Big O 기호를 사용하여 표혐함.이때, 시간 복잡도의 입력값 크기는 점근적(asymptotically)으로 증가해서 결국 무한대까지갈 수 있음.시간 복잡도의 측정방법은 알고리즘이 수행하는 기본적인 연산이 몇 개 인지를 세어서 확인함. 표기기호Big O(O) : 상한(upper bound)을 의미함.Big Omega(Ω) : 하한(lower bound)을 의미함.Big Theta(Θ) : Big O 와 Big Omega가 같을 때를 의미함. 일반적인 시간복잡도 정리표명칭복잡도 수준실행시간(T(n))실행시간 예예제 알고리즘constant time(상수시..