1주차_시간 복잡도, 공간 복잡도, 점근표기법

시간 복잡도

 

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

입력값이 늘어나도 시간이 덜 늘어나는 알고리즘을 짜기 위해 알아야 함!!

 

각 줄이 실행되는걸 1번의 연산이 된다고 생각하여 계산!!

 

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

 

위에서 연산된 것들을 더해보면,

1. (array의 길이) X (array의 길이) X (비교 연산 1번)

array(입력값)의 길이는 보통 N이라고 표현하면

N^2라고 할 수 있다.이 함수는 N^2 만큼의 시간이 걸렸다!

 

 

한가지 예를 더 보자

 

def find_max_num(array):
    max_num = array[0]        
    for num in array:      
        if num > max_num:  
            max_num = num
    return max_num

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

 

 

위에서 연산된 것들을 더해보면,

1. max_num 대입 연산 1번
2. array의 길이 X (비교 연산 1번 + 대입 연산 1번)

array 의 길이를 N이라고 하면 1 + 2 X N

이 함수는 2N + 1 만큼의 시간이 걸렸다!

 

예제들을 보고 어떤 코드가 시간복잡도가 더 좋은건지 어떻게 비교하면 되냐!

아래 글을 읽어보면 지수만 비교하면 된다.

수가 작을때는 차이가 작아도 숫자가 커지면 지수가 클수록 어마어마하게 커지는걸 확인할 수 있다!!

앞으론 지수를 비교하자!

 

---

공간복잡도 

 

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

입력값이 2개로 늘어났을 때 문제를 해결하는데 걸리는 공간은 몇배로 늘어나는지 확인하기 위함!

공간이 적게 늘어나는 알고리즘이 좋은 알고리즘!

 

저장하는 데이터의 양이 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

26 + 3 = 29

29 만만큼의 공간이 사용되었다! 

 

 

두번째

 

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 만큼의 공간이 사용되었다!

 

 

 

첫번쨰, 두번째 둘 다 상수라 비교할 수 없다

 

시간복잡도로 비교하는게 더 중요하다!

---

 

점근표기법

 

알고리즘의 성능을 수학적으로 표기하는 방법

효율성을 평가하는 방법

 

1. 빅오 표기법(Big-O)

: 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지

 

2. 빅오메가 표기법(Big-Ω)

: 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지

 

예를 들어

 

빅오 표기법으로 표시하면 O(N),

빅 오메가 표기법으로 표시하면 Ω(1) 의 시간복잡도를 가진 알고리즘