시간 복잡도 문제를 풀기 전에 정리를 위해 작성.
- 시간 복잡도(Time Complexity)란?
-
입력을 나타내는 문자열 길이의 함수
-
크기 n의 모든 입력에 대해 걸리는 최대의 시간
-
알고리즘 실행시 동작하는 모든 연산의 횟수 (시간의 개념으로 접근하면 어려울 수 있다.)
-
최선, 평균, 최악 중 최악의 경우로 알고리즘의 성능을 파악
- 시간 복잡도 표현 방법 Big O(빅 오), Big Omega(빅 오메가, Big Theta(빅 세타)
1-1. O (Big O)
-
최악의 성능 즉, 최대 실행 시간을 나타냅니다.
-
효율성을 상한선 기준으로 표시 (모든 경우의 수를 포함한다)
-
영향력이 없거나 낮은 차수의 항은 무시한다.
ex_ O(2N²+N) = O(N²) -
상수는 무시한다.
ex_ O(N+2) = O(N)/O(7) = O(1)
성능 비교 ( 제일 빠른 O(1) ):
- 빠름: O(1) < O(logn) < O(N) < O(NlogN) < O(N²) < O(2²) : 느림
