시간 복잡도

시간 복잡도(Time Complexity)

시간 복잡도는 알고리즘이 입력 코기(n)에 따라 얼마나 많은 연산을 수행하는지를 수학적으로 표현한 것이다.

보통 알고리즘의 효율성과 실행 속도를 평가하기 위해 사용된다.

 

시간 복잡도는 주로 세 가지 표기법으로 분류된다.

 

빅-오(Big-O)

최악의 경우(Worst Case)를 나타내며, 가장 많이 사용되는 표기법이다. 알고리즘이 가장 오래 걸리는 상황에서의 연산 횟수를 설명한다.

 

빅-오메가(Big-Ω)

최선의 경우(Best Case) 를 나타내며, 가장 적게 걸리는 상황에서의 연산 횟수를 설명한다.

 

빅-세타(Big-Θ)

상한과 하한이 같을 때 사용되며, 정확한 수행 시간을 나타낸다.

 

예시

다음은 1~100 사이에서 무작위 숫자를 뽑고, 해당 숫자를 찾을 때까지 순회하는 알고리즘이다.

 

import random

randNumber = random.randrange(1, 101)

for i in range(1, 101):
    if i == randNumber:
        print(i)
        break

 

Best Case

뽑은 숫자가 1일 경우, 단 1번만에 찾는다 → Ω(1)

 

Average Case

1 일 때 1번

2 일 때 2번

...

n 일 때 n번

 

전체 평균 횟수를 계산하면 1 + 2 + ... + n으로 등차수열을 계산하면 n(n + 1) / 2, 이는 입력 크기 n이 커질수록 선형적으로 증가하므로, Average Case는 O(n)으로 표현한다.

 

Worst Case

뽑은 숫자가 100일 경우, 100번 순회 → O(n)