시간복잡도(Time Complexity) & 공간복잡도(Space Complexity)

복잡도란,

1. 알고리즘의 성능, 효율성을 나타내는 척도
2. 크게 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다.
3. 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다.

시간복잡도(Time Complexity)

- 알고리즘이 특정 입력 크기에 대해 얼나마 빠르게 동작하는지를 나타낸다.

- 연산의 수가 입력의 크기에 따라 어떻게 변화하는지를 빅오 표기법(Big-O notation)을 통해 나타낸다.

 

 

시간 복잡도를 표현하는데 가장 일반적으로 사용되는 표기법

 

---

시간 복잡도 판단하기

*최댓값 찾기 알고리즘의 시간 복잡도 판단해보기 

아래 최댓값을 찾는 두가지 코드 중에 어느 것이 더 좋은 알고리즘인지 가볍게 확인해보자!

 

첫 번째 방법

def find_highest_value(data_list):
        for candidate in data_list:
            is_highest = True
            for comparison_value in data_list:
                if candidate < comparison_value:
                    is_highest = False
            if is_highest:
                return candidate

    print("정답 = 25 / 현재 풀이 값 = ", find_highest_value([10, 25, 13, 8, 7, 15]))

• for candidate in data_list: data_list의 길이만큼 아래 연산이 실행
• for comparison_value in data_list: data_list의 길이만큼 아래 연산이 실행
• if candidate < comparison_value: 비교 연산 1번 실행
• is_highest = False: 대입 연산 1번 실행

전체 시간복잡도는 대략 N * N * 2 만큼의 시간이 필요하다. 즉, 이 함수는 2 * N^2 + N 만큼의 시간이 걸린다.

 

 

두 번째 방법

    def find_highest_value(data_list):
        highest_value = data_list[0]
        for current_value in data_list:
            if current_value > highest_value:
                highest_value = current_value
        return highest_value

    print("정답 = 25 / 현재 풀이 값 = ", find_highest_value([10, 25, 13, 8, 7, 15]))

• highest_value = data_list[0]: 연산 1번 실행
• for current_value in data_list: data_list의 길이만큼 아래 연산이 실행
• if current_value > highest_value: 비교 연산 1번 실행
• highest_value = current_value: 대입 연산 1번 실행

따라서 전체 시간복잡도는 1 + 2 * N이 된다. 즉, 이 함수는 2N + 1 만큼의 시간이 걸린다.

 

아래 표를 통해 두 가지 경우에 따라 연산이 얼마나 달라지는지 체감이 된다.

2 * N^2 + N  vs 2N+1

 

 

---

공간 복잡도 판단하기

공간복잡도란

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

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

 

*최빈값 찾기 알고리즘의 공간 복잡도 판단하기

 

첫 번째 방법

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
    
    print("정답 = i 현재 풀이 값 =", find_max_occurred_alphabet("hello my name is lcm"))

 

• 위에서 사용된 공간들을 더해보면,
  1. alphabet_array 의 길이 = 26
  2. max_occurrence, max_alphabet, occurrence 변수 = 3

29

 

두 번째 방법

def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26 # -> 26 개의 공간을 사용합니다

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a') # 1개의 공간
        alphabet_occurrence_array[arr_index] += 1

    max_occurrence = 0 # 1개의 공간
    max_alphabet_index = 0 # 1개의 공간
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index] # 1개의 공간
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

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


result = find_max_occurred_alphabet
print("정답 = i 현재 풀이 값 =", result("hello my name is lcm"))

 

• 위에서 사용된 공간들을 더해보면,
  1. alphabet_array 의 길이 = 26
  2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4

30

 

 

사실 상 29와 30은 모두 상수라서 큰 상관이 없다.

공간 복잡도가 동일한 계수일 경우, 시간 복잡도로 비교하면 된다.

 

이처럼 대부분의 문제에서 알고리즘의 성능이 공간에 의해 무조건 결정되지는 않는다.

따라서 공간복잡도 보다는 시간 복잡도를 더 신경 써야할때도 있다. 

 

---

 

 

 

이상입니다!