Time Complexity 시간 복잡도

빅 오 표기법, 빅 세타 표기법

시간 복잡도 (Time Complexity)

시간 복잡도는, 알고리즘 효율성을 판단하는 중요 척도 (시간 복잡도, 공간 복잡도) 중 하나임

시간 복잡도의 특징

시간 복잡도의 산정 기준 : 연산 수

• 소요되는 기본 연산 수에 의거함
  • 주로, 알고리즘이 사용한 기본 연산의 수(명령 수,스텝 수)에 따름
  • 여기서, 주요 기본 연산으로는, 데이터의 비교,덧셈,곱셈,나눗셈 등이 있음

시간 복잡도의 표현 방식 : 함수적

• 기본 연산 수가 입력 크기(n : 입력의 개수)와 어떤 함수 관계가 있는가를 분석하고,
  • 여기서, 입력 크기의 ex는,
    • 정렬을 하려는 경우 : 정렬 대상이 되는 원소의 수
    • 계승 계산을 하는 경우 : 계승 계산을 하고자 하는 자연수
    • 최단거리를 구하는 경우 : 노드의 수 및 간선의 수
• 이를 함수식 처럼 표현 함

시간 복잡도의 분석 방법 : 점근적

• 입력 크기가 무한히 증가할 때, 알고리즘이 어떻게 작동하는가에 대해서 따지는,
• 점근적 분석 방법을 씀

시간 복잡도의 분석 종류 : (아래 2.항 참조)

• (최악의 경우) => big-O (빅 오 표기법) : O() => 최악, 이정도는 보장 (점근적 상한선)
• (최선의 경우) => big-Omega (빅 오메가 표기법) : Ω() => 최고 수준 (점근적 하한선)
• (평균의 경우) => big-Theta (빅 세타 표기법) : Θ() => 대략

시간 복잡도의 계산 방식

• 주로, 빅 오 표기법(점근적 상한선)에 준하여,
• 전체 값 계산에 가장 큰 영향을 주는 항 만 고려함 (즉, 최악의 시나리오)
• 즉, 근사적인 것을 구함

시간 복잡도의 분석 종류

최악의 경우

• big-O (빅 오 표기법) : O() => 기껏해야 . 점근적 상한선
  • 입력 크기가 무한대로 갈 때 점근적 상한
  • (아무리 나빠도 시간이 이보다 덜 걸림. 즉, 최악의 시나리오) . 주로, 빅 오 표기법을 사용함

최선의 경우

• big-Omega (빅 오메가 표기법) : Ω()=> 적어도 . 점근적 하한선
  • (최소 이만한 시간이 걸림, 최선의 시나리오)

평균의 경우

• big-Theta (빅 세타 표기법) : Θ() => 대략 . 빅 오,빅 오메가 표기법의 절충 (즉,교집합)

시간 복잡도의 주요 계산 예시

• 가장 큰 차수 만 고려 : ex) n² + n + 1 => O(n²)
• 계수는 1 로 함 : ex) 3n => O(1n) => O(n)
• 작은 차이는 무시 : ex) O(n-1) => O(n)
• 규모가 큰 것 만 고려 : ex) O(2ⁿ + n²) => O(2ⁿ)

시간 복잡도의 주요 표기 예시

☞ 시간복잡도 표기 예 참조

• O(c) 또는 O(1) : 상수 시간 알고리즘 (constant time algorithm)
• O(log n) : 로그 시간 알고리즘 (logarithmic time algorithm)
• O(n) : 선형 시간(1차 시간) 알고리즘 (linear time algorithm)
• O(n log n) : n 로그 시간 알고리즘 (nlogn time algorithm)
• O(n²) : 평방 시간(2차 시간) 알고리즘 (quadratic time algorithm)
• O(n³) : 3차 시간 알고리즘
• O(2ⁿ) : 지수 시간
• O(n!) : 계승 시간 (Factorial Time Algorithm)
• O(∞) : 종료되지 않는 무한 루프

[참고] 시간복잡도 연산 크기 순서

• O(1) < O(log n) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(∞)

원문

• Time Complexity 시간 복잡도