1.배운 것

① 코드의 효율성을 알아보는 방법

② 효율성을 표기하는 방법

2.시간복잡도

① 정의: 입력값 크기와 연산 소요 시간 사이의 상관관계

② 예시: 다음과 같은 코드를 계산하데 '2N+1' 시간이 소요된다.

▶ 여기서 N은 입력값 길이를 의미함

def find_max_num(array):
    max_num = array[0]        # 1. 입력 1번, 누적: 1
    for num in array:         # 2. array 길이만큼 연산, 누적: 1 + N
        if num > max_num:     # 2. if문 비교 1번, 누적: 1 + N*(1)
            max_num = num     # 2. if문 입력 1번, 누적: 1 + N*(1+1)
    return max_num            # 시간 복잡도 결과: 1 + 2N

③ 계산법

- 구문 단위로 분리(위 #1., #2.으로 분리됨)

- 함수 인자(array)가 포함된 for문만 'N'사용 가능

- for문 안에 다른 구문이 있다면 곱하기

- 결과는 구문 단위 시간 복잡도 모두 더하기

④ 의미해석

- N의 지수가 커질수록 시간복잡도 급격히 증가

- 줄(line)수가 많아질수록 시간복잡도 증가

3.공간복잡도

① 정의: 입력값 크기와 차지하는 공간 사이의 상관관계

② 예시: 다음과 같은 코드를 계산하는데 '29' 공간이 필요하다.

input = "hello my name is study"

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"]  #26개 공간 사용, 누적: 26
    max_occurrence = 0                                                                                                                              #1개 공간 사용, 누적: 27
    max_alphabet = alphabet_array[0]                                                                                                                #1개 공간 사용, 누적: 28

    for alphabet in alphabet_array:
        occurrence = 0                                                                                                                              #1개 공간 사용, 누적: 29
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet

③ 계산법

- 변수별 사용되는 공간 합산

- 반복되는 변수는 1번만 더하기

④ 의미해석

- 변수의 갯수가 많아질수록 공간복잡도 증가

4.소결론

① 시간 복잡도가 더 중요하다

- (시) N이 증가함에 따라 시간 복잡도의 급증이 나타남

- (시) 시간 복잡도의 증가는 계산량의 증가를 의미함

- (시) 계산량 증가는 곧 처리량 증가를 의미하므로, 결과 도출 시 더 많은 시간이 소비됨

- (공) N의 크기에 따라 변화를 감지하기 어려움

5.점근표기법

① 정의: 시간복잡도의 크기를 특정 문자를 사용하여 표시하는 방법

② 종류: 빅오 표기법, 빅오메가 표기법

- 빅오 표기법(=O(N)): 결과 도출까지 소비되는 최대 연산량

- 빅오메가 표기법(=Ω(N): 결과 도출까지 소비되는 최소 연산량

③ 계산법(예시)

- 결과: O(N), Ω(1)

- 계산 방법: N의 지수만 고려함

▶ N의 계수, 상수는 모두 버리기

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


def find_max_plus_or_multiply(array):
    mult_sum = 0                            #1.대입 연산, 1
    for a_num in array:                     #2.array 크기만큼, N
        if a_num <=1 or mult_sum <= 1:      #2.비교연산, N(1)
            mult_sum += a_num               #2.대입연산, N(2)
        else:
            mult_sum *= a_num

    return mult_sum                          #점근 표기법 결과: O(N))
    					     #시간 복잡도 결과: 2N+1)
    
result = find_max_plus_or_multiply(input)
print(result)

④ 의미해석

- 입력값의 배열에 따라 연산량의 차이가 발생함

- 이에 따라 최소, 최대 연산량 표시

- 보통은 최악의 상황을 고려해 최대 연산량을 표시함(O(N))

6.총결론

① 시간 복잡도가 더 중요하다.

② 시간 복잡도 중에서 빅오 표기법을 사용하자.

③ 빅오 표기법으로 표시한 연산량이 적을수록 효율적인 코딩이다.