[알고리즘] 시간복잡도

알고리즘 수행시간 문제를 푸는 도중 식이 이해가 가지 않아 공부한 내용을 정리했다

시간복잡도(Time Complexity)

알고리즘을 실행하는데 필요한 시간 척도

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

시간 복잡도 분석방법

입력 크기가 무한히 증가할 때, 알고리즘이 어떻게 작동하는가에 대해서 따질 때, 점근적(Asymptotic) 분석 방법을 사용함

점근적 분석 종류

Ω() : 오메가(big-Omega)

• 최선 => 최고 수준, 점근적 하한(aymptotic lower bound)

Θ() : 세타(big-Theta)

• 평균 => 대략, 점근적 치밀 경계(aymptotic tight bound)

O() : 빅 오(big-O)

• 최악 => 이정도는 보장, 점근적 상한(aymptotic upper bound)

---

분석법 비교

아래의 python 함수를 통해 각각을 비교해 보겠다

# 리스트(lst) 에서 원하는 값(target)을 찾는 함수
def find_value(lst, target):
    for element in lst:
        if element == target:
            return True
    return False

오메가(Ω)

오메가(Ω) 표기법은 최상의 경우이기 때문에 무조건 리스트의 첫번째에 있다고 가정한다

따라서 1번 실행하면 바로 값이 나오기 때문에 시간복잡도는 Ω(1)

세타(Θ)

세타(Θ) 표기법은 배열에서 찾는 값이 배열의 첫 번째 요소에 있을 때는 한 번의 반복만으로 찾을 수 있지만,

배열에 찾는 값이 없거나 맨 마지막에 있을 때는 모든 요소를 확인해야 한다. 따라서 이 경우 시간 복잡도는 Θ(n)

빅오(O)

빅오(O) 표기법은 알고리즘의 최악의 경우를 나타냅니다. 배열을 처음부터 끝까지 모든 요소를 확인하여 원하는 값을 찾는다. 이때, 시간 복잡도는 O(n)

• 빅오(O)를 사용하는 이유?

간결함과 단순성:
빅오 표기법은 알고리즘의 최악의 경우를 간단하고 명확하게 표현할 수 있다. 세타 표기법은 빅오보다 조금 더 복잡하며 계산하기 어려울 수 있다. 그래서 대부분의 경우 빅오 표기법으로도 충분히 알고리즘의 성능을 파악할 수 있다.

최악의 경우에 대한 보장:
빅오 표기법은 알고리즘의 최악의 경우를 나타내기 때문에, 어떤 입력이 주어지더라도 알고리즘이 해당 시간을 초과하지 않음을 보장한다. 시스템이 실시간 응답을 요구하는 경우에는 최악의 경우 시간이 예측 가능하고 예상치 못한 지연을 피하기 위해 빅오 표기법을 사용한다.

빅오(O) 시간복잡도

위로 갈수록 간단하고, 아래로 갈수록 복잡

여기서 $log~n$ 은 $log_2~n$ 을 뜻함

O(1)	상수(constant) 형태
O($log~n$)	로그 형태
O(n)	선형 형태
O($n~log~n$)	선형로그 형태
O($n^c$)	다차(polynomial) 형태
O($c^n$)	지수(exponential) 형태
O($n!$)	팩토리얼(factorial) 형태

예를 들어 연산 횟수가 $3n^3 - 5n^2 + 1$ 일 경우 시간복잡도는

O($n^3$)가 된다

$- 5n^2 + 1$ 부분도 분명 영향을 끼치지만 빅오에서는 $n$이 커질 경우 다른 항들의 영향이 미미하기 때문에 단순하게 최고차항만 계산한다

예시처럼 표에서도 단계에 따라 $n$이 커지면 커질수록 알고리즘의 시간 차이는 극명하게 벌어진다