항해99 13주차 WIL

시간복잡도

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어날까

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 max_num

result = find_max_num(input)

시간 복잡도 계산방법 :
array의 길이 X array의 길이 X 비교 연산 1번
array(입력값)의 길이는 보통 N이라고 표현

$N \times 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)

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

$1+2\times N$

---

N의 길이	$N^2$	$2N+1$
1	1	3
10	100	21
100	10000	201
1000	1000000	2001
10000	100000000	20001

상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악하면 된다.

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

---

공간복잡도

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
입력값이 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"]
    # -> 26 개의 공간을 사용합니다
    
    max_occurrence = 0 # 1개의 공간을 사용합니다
    max_alphabet = alphabet_array[0] # 1개의 공간을 사용합니다.

    for alphabet in alphabet_array:
        occurrence = 0 # 1개의 공간을 사용합니다
        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

총 29 만큼의 공간이 사용되었음.

공간복잡도가 커도 성능에 별로 차이점이 없다.
알고리즘의 성능이 공간에 의해서 결정되지는 않는다. 따라서 공간 복잡도 보다는 시간 복잡도에 신경을 써야 한다.

---

점근표기법

알고리즘의 성능을 수학적으로 표기하는 방법.
알고리즘의 “효율성”을 평가하는 방법.
점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다.

빅오 표기법

• 최악의 성능이 나올 때 어느 정도의 연산량이 걸리는가

빅오메가 표기법

• 최선의 성능이 나올 때 어느 정도의 연산량이 걸리는가

알고리즘은 입력값에 따라서 성능이 달라질 수 있다.

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

def is_number_exist(number, array): 
    for element in array: # array 의 길이만큼 아래 연산이 실행
        if number == element:  # 비교 연산 1번 실행 
            return True
    return False


result = is_number_exist(3, input)

입력값이 좋을때 Ω(1) 입력값이 안좋을 때 O(N)

알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석한다.
대부분의 입력값이 최선의 경우일 가능성은 굉장히 적고, 최악의 경우를 대비해야 한다.

빅오 표기법 예
O(logN), O(N), O($N^2$), ...
시간복잡도가 2N+1일 때 상수는 버리고 O(N)으로 작성한다.

13주 끝

알고리즘 수업을 계속 들으면서 앞으로 파이널 프로젝트를 급하게 마무리 하느라 보완사항을 정리하고, 로딩속도 개선과 기회가 되면 리액트 네이티브로도 적용해 볼 생각이다.