• 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측

시간 복잡도 정의하기

실제 시간 복잡도를 정의하는 3가지 유형

• 빅-오메가: 최선
• 빅-세타: 보통
• 빅-오: 최악

코테에서는 빅-오 기준으로 수행 시간 계산하는 것이 좋다

예로 시간 제한이 2초이면 2억 번 이하 연산 횟수로 문제를 해결해야 한다.

연산 횟수 계산 방법

• 연산횟수 = 알고리즘 시간 복잡도 x 데이터 크기

알고리즘 적합성 평가

예로 for문 100만 수행일때

• 버블 정렬 = (1000000)^2 = 1,000,000,000,000 > 200,000,000 -> 부적합
• 병합 정렬 = 1000000log(1000000) = 20,000,000 < 200,000,000 -> 적합

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준

• 예를들어 n이 10만이고
  n번 만큼 for문이 1개이건 3개이건 모두 O(n)으로 같다.
  1n, 3n 상수 제외

• 2중 for문
  n이 10만
  2중 for문 모두 n만큼 돌 때 n의 제곱 o(n)^2
  가장 많이 중첩된 반복문 기준으로 도출해서 위 반복문 외에 다른 반복문이 있더라도 시간 복잡도는 o(n)^2가 유지된다.

Big-Oh 시간 복잡도 순서

𝑂(1) < 𝑂(log n) < 𝑂(n) < 𝑂(nlog n) < 𝑂(n^2) < 𝑂(n^3) < 𝑂(2^n) < 𝑂(n!)