개발_TIL | 2022-07-21 (65)

알고리즘 2일차 공부

🕰 시간 복잡도 판단하기

• 시간 복잡도란?
  • 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계
• 시간 복잡도 계산하기 (최대값 찾기 예시)
  • 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하면 됨
  • input=[3,5,6,1,2,4] for num in array: # array 의 길이만큼 아래 연산이 실행 for compare_num in array: # array 의 길이만큼 아래 연산이 실행 if num < compare_num: # 비교 연산 1번 실행 break else: return num
  • array(입력값)의 길이는 N이라고 표현
  • 즉 위에 연산된것을 더해보면 N * N + 1
  • N²만큼의 시간이 걸렸겠구나 계산 가능
• 두번째 시간 복잡도 계산하기
  • 1 + 2 * N
• input = [3, 5, 6, 1, 2, 4] 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

• 위의 표로 깨달아보기
  • N과 N² 은 N 이 커질 수록 더 큰 차이가 남
  • N의 지수를 먼저 비교하여 시간복잡도를 분석하면 좋음
  • 상수는 신경 쓸 필요 없음
• 입력값이란?
  • 함수에서 크기 혹은 길이가 변경 될 수 있는 값
  • 수식으로 표현해야 올바른 알고리즘의 시간 복잡도를 구할 수 있음
  • 🪐공간 복잡도 파악하기
  • 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
  • 저장하는 데이터의 양이 1개의 공간을 사용한다
  • # 첫번째 방법 공간복잡도 파악 (29개 공간) input = "hello my name is sparta" 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","w","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_occurrence = occurrence
            max_alphabet = alphabet

    return max_alphabet

result = find_max_occurred_alphabet(input)
print(result)
```

```python
# 두번째 방법 공간복잡도 파악   (30개 공간)

def find_max_occurred_alphabet(string):
    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(len(alphabet_occurrence_list)):
        alphabet_occurrence = alphabet_occurrence_list[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("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
```

⁉️ 그러면 공간을 더 적게 쓴 첫번째 방법이 더 효율적일까?

- 그렇지 않음! 성능에 아무런 차이가 없다!
- 29와 30 모두 상수라 큰 상관이 없음
- 시간 복잡도로 비교하면 됨
- 첫번째 시간복잡도

```python
for alphabet in alphabet_array:    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        occurrence = 0                  # 대입 연산 1번 실행
        for char in string:             # string 의 길이만큼 아래 연산이 실행
            if char == alphabet:        # 비교 연산 1번 실행
                occurrence += 1         # 대입 연산 1번 실행 

        if occurrence > max_occurrence: # 비교 연산 1번 실행
            max_alphabet = alphabet     # 대입 연산 1번 실행
            max_occurrence = number     # 대입 연산 1번 실행
```

1. alphabet_array 의 길이 X 대입 연산 1번
2. alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번)
3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번)
4. 위의 연산식 26 * (1 + 2 * N + 3) = 52N + 104
- 두번째 시간복잡도

```python
for char in string:        # string 의 길이만큼 아래 연산이 실행
        if not char.isalpha(): # 비교 연산 1번 실행
            continue
        arr_index = ord(char) - ord('a')         # 대입 연산 1번 실행 
        alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행 

    max_occurrence = 0        # 대입 연산 1번 실행 
    max_alphabet_index = 0    # 대입 연산 1번 실행 
    for index in range(len(alphabet_occurrence_list)):    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행 
        if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행 
            max_occurrence = alphabet_occurrence # 대입 연산 1번 실행 
            max_alphabet_index = index           # 대입 연산 1번 실행
```

1. string의 길이 X  (비교 연산 1번 + 대입 연산 2번) 
2. 대입 연산 2번 
3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)
4. 위의 연산식 N * ( 1 + 2 ) + 2 + 26  * ( 1 + 3 ) = 3N + 106



`공간복잡도 보단` `시간복잡도를 중요`하게 생각!

N²에 비하면 아무것도 아님

# 점근 표기법

- `점근 표기법`이란?
- 알고리즘의 성능을 `수학적으로 표현`하는 것

점근 표기법 종류

- 점근 표기법의 종류에는 
**`빅오(Big-O)`, `빅 오메가(Big-Ω)`**이 있습니다.
- **`빅오(Big-O)` :** 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지
- **`빅 오메가(Big-Ω)` :** 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지

```python
def is_number_exist(number, array):
for element in array:     # array 의 길이만큼 아래 연산이 실행
        if number == element: # 비교 연산 1번 실행 
            return True  # N * 1 = N만큼
    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]))
```

알고리즘은 사용자의 입력값에 의해 속도가 좌우되기 때문에,

최선인 빅 오메가보다, 최악인 빅오를 자주 사용하게 될 것

# 🍭 알고리즘 문제 접근 기억하기

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