시간복잡도

시간복잡도 : 주어진 문제를 해결하기 위한 연산 횟수, 일반적으로 파이썬은 2000 만번 ~ 1억 번의 연산을 1초의 수행 시간으로 예측할 수 있습니다.

 

• 시간 복잡도 유형
  1. 빅-오메가 ( Ω(n) ) : 최선일 때의 연산 횟수를 나타낸 표기법
  2. 빅-세타 ( Θ(n) ) : 보통(평균) 일 때의 연산 횟수를 나타낸 표기법
  3. 빅-오 ( O(n) ) : 최악일 때의 연산 횟수를 나타낸 표기법 -> 가장 많이 사용함
• 코딩 테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?
  
  • -> 코딩 테스트에서는 빅-오 표기법 ( O(n) ) 기준으로 수행 시간을 계산하는 것이 좋습니다.  

 

빅-오 표기법 ( O(n) ) 의 주요 시간 복잡도 종류

 

O(N) : 5N+3, 2N+10logN, 10N
O(N^2) : N^2+2n+4, 6N^2+12logN
O(NlogN) : NlogN + 30N+ 10, 3NlogN
O(logN) : 3logN, logN+3
O(1): 5, 16, 46

상수 시간	O(1)	입력 크기와 상관없이 항상 일정한 시간 ex) 배열에서 인덱스로 값 찾기
로그 시간	O(log n)	입력이 커질수록 느리게 증가 ex) 이진 탐색
선형 시간	O(n)	입력 크기에 비례 ex) 배열 전체 순회
로그-선형	O(n log n)	정렬 알고리즘에서 자주 등장 ex) 머지 정렬, 퀵 정렬 평균
제곱 시간	O(n²)	중첩 반복문 등 ex) 버블 정렬, 삽입 정렬
지수 시간	O(2^n)	매우 느림. 입력이 조금만 커져도 실행 시간이 급증 ex) 부분집합, 재귀 백트래킹
팩토리얼 시간	O(n!)	극도로 느림. ex) 순열 계산, 완전탐색(브루트포스)