시간 복잡도

Time Complexity

시간 복잡도 시간 복잡도 (Time Complexity)는 프로그램의 입력값와 연산 수행 시간의 상관관계를 나타내는 척도를 말한다. 수치가 낮으면 낮을수록 더 효율적인 알고리즘을 뜻한다. 일반적으로 알고리즘에서 효율성을 따질때는 프로그램이 돌아가는 하나하나의 단계를 따지는 게 아닌, 시간 복잡도를 사용하게 된다. 하나하나 단계별로 효율성을 결정하기는 매우 어렵기 때문이다. 시간 복잡도는 크게 3가지 표기법으로 나타낼 수 있다. Big-O - 최악의 경우 (해당 알고리즘은 Big-O보다 더 오래 걸릴 수 없다) Big-Ω - 최선의 경우 (해당 알고리즘은 Big-Omega보다 더 빠를 수 없다) Big-θ - 평균의 경우 (Big-O + Big-Omega를 합쳐 표현한 것과 같음) 이 중에서 최악의 상황을..