lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

pythonIntroStep4Chapter3Title

pythonIntroStep4Chapter1Title

pythonIntroStep4Chapter2Title

# 반복을 사용한 피보나치 수열 (공간 복잡도 O(1))
def fibonacci_iterative(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

# 반복 방식 사용 예시
n = 10
print(f"{n}번째 피보나치 수: {fibonacci_iterative(n)}")  # 10번째 피보나치 수: 55


# 재귀를 사용한 피보나치 수열 (공간 복잡도 O(n))
def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# 재귀 방식 사용 예시
n = 10
print(f"{n}번째 피보나치 수: {fibonacci_recursive(n)}")  # 10번째 피보나치 수: 55

# 알고리즘의 시간, 공간 복잡도

알고리즘의 복잡도를 이해하기 위한 간단한 파이썬 코드 예시를 확인해 보겠습니다.

<br />

## 시간 복잡도

시간 복잡도(Time Complexity)는 알고리즘이 문제를 해결하는 데 소요되는 시간이 입력 크기에 따라 어떻게 변하는지를 나타내는 척도입니다.

### 선형 시간 복잡도 (O(n)) 예시

선형 시간 복잡도를 가지는 알고리즘은 입력 크기에 직접 비례하여 시간이 증가합니다. 아래 코드는 주어진 리스트의 각 요소를 출력하는 간단한 예입니다.

```python title="선형 시간 복잡도 예시"
numbers = [1, 2, 3, 4, 5]

for number in numbers:
    print(number)
```

이 코드에서 `for` 루프는 리스트 `numbers`의 각 요소를 한 번씩 방문하므로, 리스트의 크기(n)에 비례하는 시간이 소요됩니다.

<br />

### 이차 시간 복잡도 (O(n²)) 예시

이차 시간 복잡도를 가지는 알고리즘은 입력 크기의 제곱에 비례하여 시간이 증가합니다. 아래 코드는 중첩된 루프를 사용하여 각 숫자 쌍의 조합을 출력합니다.

```python title="이차 시간 복잡도 예시"
numbers = [1, 2, 3, 4, 5]

for i in numbers:
    for j in numbers:
        print(f"({i}, {j})")
```

이 코드에서 두 개의 중첩된 `for` 루프는 리스트 `numbers`의 모든 가능한 숫자 쌍을 생성합니다. 첫 번째 루프가 한 번 실행될 때마다 두 번째 루프가 전체 리스트를 순회하므로, 전체 작업 횟수는 `n x n`, 즉 n의 제곱에 비례합니다.

<br />

## 공간 복잡도

공간 복잡도는 알고리즘이 실행될 때 필요한 메모리 공간의 양을 나타내며, 알고리즘이 사용하는 변수, 데이터 구조 및 할당된 메모리 양에 의해 결정됩니다.

### 상수 공간 복잡도 (O(1)) 예시

상수 공간 복잡도는 입력 크기에 상관없이 알고리즘이 사용하는 메모리 양이 일정한 경우입니다. 예를 들어, 특정 수의 제곱을 계산하는 함수는 입력 크기와 상관없이 일정한 양의 메모리만을 사용합니다.

```python title="상수 공간 복잡도 예시"
def square(number):
    return number * number

result = square(5)

print(result)
```

이 함수는 number라는 단 하나의 입력과, 그 입력의 제곱을 계산하는 임시 변수만을 사용합니다. 따라서, 이 함수의 공간 복잡도는 O(1)입니다.

<br />

### 선형 공간 복잡도 (O(n))

선형 공간 복잡도는 알고리즘이 사용하는 메모리 양이 입력 크기에 비례해 증가합니다. 예를 들어, 입력 리스트의 모든 요소를 복사하여 새로운 리스트를 만드는 경우가 이에 해당합니다.

```python title="선형 공간 복잡도 예시"
def clone_list(original_list):
    new_list = original_list[:]  # 리스트 전체를 복사
    return new_list

original = [1, 2, 3, 4, 5]
cloned = clone_list(original)

print(cloned)
```

이 함수에서 new_list는 입력 original_list의 크기만큼의 공간을 차지합니다. 입력 리스트의 크기가 n이라면, 복제된 리스트도 n만큼의 공간을 필요로 하므로, 이 함수의 공간 복잡도는 O(n)입니다.