시간복잡도, 공간 복잡도, 점근 표기법

 ✅ 알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석합니다.

왜냐면 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러, 우리는 최악의 경우를 대비해야 하기 때문입니다.

 

우리는 다음만 기억하면 됩니다.

1. 입력값에 비례해서 얼마나 늘어날지 파악해보자. 1? N? N^2?
2. 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자.
3. 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자

 

 

시간 복잡도란?

• 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말합니다! 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이죠. 우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?

 

 

비교하기

• 이 표를 보면, 두 가지를 깨달을 수 있습니다.
  1. N 과 N^2 은 N 이 커질수록 더 큰 차이가 나는구나!
  2. N의 지수를 먼저 비교하면 되겠구나.
• 그러나, 저희가 매번 코드를 매 실행 단위로 이렇게 몇 번의 연산이 발생하는지 확인하는 건 불가능합니다. 따라서 상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악하면 됩니다.

💡 즉, 2N+1의 연산량이 나온 첫번째 풀이 방법은 N 만큼의 연산량이 필요하다 N^2 의 연산량이 나온 두번째 풀이 방법은 N^2 만큼의 연산량이 필요하다.

참고로, 만약 상수의 연산량이 필요하다면, 1 만큼의 연산량이 필요하다고 말하면 됩니다.

 

 

 

공간 복잡도란?

• 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말합니다! 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이죠. 우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?

• 1. 최빈값 찾기 알고리즘의 공간 복잡도 판단해보기
  • 첫 번째 방법

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

result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

 

• 이 해결 방법은 각 알파벳마다 문자열을 돌면서 몇 글자 나왔는지 확인합니다. 만약 그 숫자가 저장한 알파벳 빈도 수보다 크다면, 그 값을 저장하고 제일 큰 알파벳으로 저장합니다. 이 함수가 공간을 얼마나 사용하는지 어떻게 분석할 수 있을까요?
• 바로 저장하는 데이터의 양이 1개의 공간을 사용한다고 계산하시면 됩니다. 아래와 같이 계산할 수 있습니다.

    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"]
# -> 26 개의 공간을 사용합니다
    max_occurrence = 0 # 1개의 공간을 사용합니다
    max_alphabet = alphabet_array[0]   # 1개의 공간을 사용합니다.

    for alphabet in alphabet_array:
        occurrence = 0  # 1개의 공간을 사용합니다

• 위에서 사용된 공간들을 더해보면,
  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'))


result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

 

• 이 해결 방법은 각 알파벳의 빈도수를 저장한 다음에, 빈도 수 중 가장 많은 알파벳의 인덱스 값을 반환합니다. 다시 한 번 공간복잡도를 분석해볼까요?

		alphabet_occurrence_list = [0] * 26 # -> 26 개의 공간을 사용합니다

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')  # 1개의 공간을 사용합니다
        alphabet_occurrence_list[arr_index] += 1

    max_occurrence = 0                   # 1개의 공간을 사용합니다
    max_alphabet_index = 0               # 1개의 공간을 사용합니다
    for index in range(26):
        alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용합니다
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

• 위에서 사용된 공간들을 더해보면,
  1. alphabet_array 의 길이 = 26
  2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
  30만큼의 공간이 필요합니다. 그러면 우리는 이제 이 함수는 30 만큼의 공간이 사용되었구나! 라고 말할 수 있습니다.
•  ❓ 그러면, 공간을 더 적게 쓴 첫 번째 방법이 더 효율적인걸까요?
  • ✅ 그렇지 않습니다.그러면 뭘로 비교하는 게 좋을까요? 바로 시간 복잡도로 비교하시면 됩니다.그러면, 시간 복잡도는 차이가 있는지 분석해볼까요?
  • 29와 30 모두 상수라 큰 상관이 없습니다.
  • 이처럼, 대부분의 문제에서는 알고리즘의 성능이 공간에 의해서 결정되지 않습니다.
  • 따라서 공간 복잡도보다는 시간 복잡도를 더 신경 써야 합니다.
•  

점근 표기법이란?

• 💡 알고리즘의 성능을 수학적으로 표기하는 방법입니다. 알고리즘의 “효율성”을 평가하는 방법입니다. 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 저희가 지금까지 이 함수는 N 정도의 시간과 공간이 걸리겠구나 하면서 분석했던 게 점근 표기법의 일종이라고 말할 수 있습니다.
•  👉 점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있습니다.

• 빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지,
• 빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기합니다.
• 예를 들어 빅오 표기법으로 표시하면 O(N), 빅 오메가 표기법으로 표시하면 Ω(1) 의 시간복잡도를 가진 알고리즘이다! 라고 표현할 수 있습니다.

• 1. ✍️ 배열에서 특정 요소 찾기
  • Q. 문제 설명
    • 이 문제를 풀기 위해서는 어떻게 해야 할까요? 아래 코드를 복사 붙여넣기 하고 함수를 작성해보세요! 2분 정도 고민해 본 다음, 아래 방법들을 펼쳐 봅시다!
  • ❓ Q. 다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정 숫자가 존재한다면 True, 존재하지 않다면 False 를 반환하시오.

def is_number_exist(number, array):
    if number in array:
        return True
    else:
        return False


result = is_number_exist
print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))
print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))

•