시간복잡도

• 알고리즘의 효율성을 평가하는 척도이다
• 알고리즘 문제의 크기에 따라 얼마나 많은 시간이 필요한지 나타내는 지표이다
• 알고리즘의 입력 데이터 크기를 N이라고 할 때, 알고리즘의 실행 시간을 빅- 오 표기법을 통해 나타낸다

시간 복잡도를 표기하는 방법

• Big-O(빅-오) → 상한 점근
• Big-Ω(빅-오메가) → 하한 점근
• Big-θ(빅-세타) → 그 둘의 평균
• 시간복잡도를 각각 최악, 최선, 평균의 경우에 대해서 나타낸다. 주로 시간복잡도는 빅-오 표기법을 통해서 최악을 고려한다

빅-오 표기법

• 입력값의 크기에(N) 따라 시간이 최악의 경우 얼마나 걸릴 지를 표현한다
• 예를 들어, 선택 정렬의 경우 최선의 경우(모두 정렬되어 있는 경우)에는 O(N)의 시간이 걸리지만 모두 정렬되어 있지 않은 경우 O(N^2)의 시간이 걸리므로 O(N^2)의 시간복잡도를 가진다고 표현한다
• 최고차항만 신경쓰고 나머지 계수들은 신경쓰지 않는다