알고리즘 뿌시기 첫번째 (시간복잡도와 공간복잡도)

시작하며

스파르타 코딩클럽의 '알고보면 알기쉬운 알고리즘 52기'를 수강하기 시작했다.
오늘이 1주차 강의를 들었다.

이렇게 모여서 오티를 듣고 1주차 방에 모여서 각자 공부를 시작했다.(온라인 모각코 느낌?)

내가 일등이다.. 키킥

사유는.. 내가 모여서 수업 듣는 건 줄 모르고, 먼저 들어버려서..

오늘 수업은 재밌었다.
튜터 분 목소리도 잠 오지 않고, 귀에 쏙쏙 들어온다.
그리고 코딩이론갓기인 나에게도 이해가 될 만큼 쉽게 설명해주신다.

휴식시간에 집에서 따뜻하게 잘 듣고 계시냐고 해서..😂
회사에 있는 나를 함께 슬퍼해주셨다..

이제.. 서론을 떨구고 오늘 공부한 내용을 주저리 해보도록 하겠다.

시간복잡도

시간복잡도란?

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

입력값이 N배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 함수.

최댓값 찾기 알고리즘의 공간 복잡도 구하기

아래 코드는 입력한 array에서 최댓값을 반환하는 코드이다.

input = [3, 5, 6, 1, 2, 4]


def find_max_num(array):
    for num in array:              # array 의 길이만큼 아래 연산이 실행
        for compare_num in array:  # array 의 길이만큼 아래 연산이 실행
            if num < compare_num:  # 비교 연산 1번 실행
                break
        else:
            return num


result = find_max_num(input)

입력값 input의 길이를 N이라고 했을 때, 비교 연산이 N * N 번 실행된다.
고로 이 함수의 시간복잡도는 $N^2$ 이다.


아래의 코드는 위와 같은 기능을 하는 코드이다.

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

result = find_max_num(input)

입력값 input의 길이를 N이라고 했을 때, 대입연산이 한번 비교연산이 N번 또 대입연산이 N번 실행된다.
고로 이 함수의 시간복잡도는 $1 + 2N$ 이다.

아래 표를 보면 입력값이 늘어날 수록 확연히 시간차이가 많이 난다는 것을 확인할 수 있다.
$N$이 아닌 상수(1)는 거의 계산에 영향을 주지 않는다.

N의 길이	$N^2$	$1 + 2N$
1	1	3
100	10000	201
10000	100000000	20001

공간복잡도

공간복잡도란?

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

입력값이 N배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 함수.

가장 많이 포함된 alphabet을 구하는 코드에서 공간 복잡도 구하기

아래 코드는 입력한 입력한 string에서 가장 많이 포함된 alphabet을 구하는 코드이다.

def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "z"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet

1. alphabet_array 의 길이 = 26
2. max_occurrence, max_alphabet, occurrence 변수 = 3

$29$만큼의 공간을 차지한다.
고로 공간 복잡도는 $29$이다.


아래의 코드는 위와 같은 기능을 하는 코드이다.

def find_max_occurred_alphabet(string):
    alphabet_occurrence_list = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_list[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_list)):
        alphabet_occurrence = alphabet_occurrence_list[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

    return chr(max_alphabet_index + ord('a'))

1. alphabet_array 의 길이 = 26
2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
   $30$만큼의 공간을 차지한다.
   고로 공간 복잡도는 $30$이다.
   
   

하지만 공간 복잡도는 위의 코드가 더 효율적이다.
하지만 시간 복잡도로 본다면,
위의 코드는 아래와 같고,
$26*(1 + 2*N + 3) = 52N + 104$
아래 코드는 아래와 같다.
$N * (1 + 2) + 2 + 26 * (1 + 3) = 3N + 106$

상수를 빼고 보면 $O(52N) 과 O(3N)$이다.

알고리즘에서 중요도 - 시간 복잡도 > 공간 복잡도

위 같은 상황에서는 시간 복잡도만 생각하면 된다.