[Algorithms] 시간 복잡도 & 공간 복잡도

Time Complexity

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계

def find_max_num(array):
    max_num = array[0]     # 연산 1번 실행
    for num in array:      # array 의 길이만큼 아래 연산이 실행
        if num > max_num:  # 비교 연산 1번 실행
            max_num = num  # 대입 연산 1번 실행
    return max_num

위 함수의 시간 복잡도는 입력의 길이를 $n$이라 했을 때

$1 + 2\times n$

Space Complexity

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계

Asymptotic Notation

알고리즘의 성능을 수학적으로 표기하는 방법으로서 알고리즘의 효율성을 평가하는 방법이다. 점근적 표기법은 계수와 낮은 차수의 항을 제외하여 표기한다.

Big-O

빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기한다. 주로 알고리즘의 시간복잡도는 최악일 때의 성능을 고려하는 빅오 표기법을 사용하여 나타낸다.

Big-Ω

빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기한다.

예제

def is_number_exist(number, array):
    for element in array:            # array 의 길이만큼 아래 연산이 실행
        if number == element:        # 비교 연산 1번 실행
            return True
    return False

위 함수의 시간 복잡도는 $1\times n$ 이 되어

$T(n) = n$

Worst case는 찾고자 하는 숫자가 마지막에 존재하는 경우이므로

$T(n) = O(n)$

Best case는 찾고자 하는 숫자가 첫 번째에 존재하는 경우이므로

$T(n) = Ω(1)$