[Python] 시간 복잡도 🕒

🕒 시간 복잡도

• 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도
• Big-O(빅-오) → 복잡도 함수의 점근적 상한을 표기 (최악을 고려)
• Big-Ω(빅-오메가) → 복잡도 함수의 점근적 하한을 표기 (최선을 고려)
• Big-θ(빅-세타) → 복잡도 함수의 점근적 상한과 하한을 동시에 만족 (평균을 고려)
• 시간 복잡도는 주로 Big-O(빅-오) 표기법을 사용한다.

🟢 Big-O 표기법 종류

O(1)	「상수 복잡도」 - 입력 값의 크기와 상관없이 시간이 일정하다. - ex) 해시 테이블의 조회 및 삽입
O(n)	「선형 복잡도」 - 입력 값의 증가에 따라 시간도 증가한다. - ex) 정렬되지 않은 리스트에서 값 탐색, 1차원 for loop
O(log n)	「로그 복잡도」 - 입력 값이 매우 큰 경우에도 시간에는 크게 영향을 받지 않는다. - 특정 요인에 의해 필요 단계가 줄어든다. - ex) 이진 탐색
O(n log n)	「선형-로그 복잡도」 - 문제 해결을 위한 단계 수가 N*(log2N) 번만큼의 수행 시간을 가진다. - ex) 병합 정렬 알고리즘, 퀵 정렬 알고리즘
O(n²)	「2차 복잡도」 - 입력 값의 증가에 따라 시간이 n²만큼 증가한다. -ex) 버블 정렬 알고리즘, 삽입 정렬 알고리즘, 2차원 for loop
O(2ⁿ)	「지수 복잡도」 - 입력 값의 크기에 따라 시간이 2ⁿ 만큼 증가한다. - 재귀적으로 계산하는 경우 - ex) 피보나치 수열
O(n!)	「팩토리얼 복잡도」