lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

pythonIntroStep4Chapter3Title

pythonIntroStep4Chapter1Title

pythonIntroStep4Chapter2Title

# 선형 검색 (시간 복잡도 O(n))
def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return f"{x}는 위치 {i}에서 발견됨"
    return f"{x}는 배열에 존재하지 않음"

# 선형 검색 사용 예시
arr = [2, 3, 4, 10, 40]
x = 10
print(linear_search(arr, x))  # 10는 위치 3에서 발견됨


# 이진 검색 (시간 복잡도 O(log n))
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:
        mid = (high + low) // 2

        # x를 찾은 경우
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return f"{x}는 위치 {mid}에서 발견됨"
    return f"{x}는 배열에 존재하지 않음"

# 이진 검색 사용 예시
arr = [2, 3, 4, 10, 40]
x = 10
print(binary_search(arr, x))  # 10는 위치 3에서 발견됨

# 알고리즘의 복잡도(Complexity)란?

알고리즘의 복잡도는 알고리즘이 얼마나 효율적인지를 측정하는 방법으로, 알고리즘의 효율성은 빅 오 표기법(Big O notation)으로 표현합니다.

- `'O' (Big O)`: '차수(Order)'를 뜻하며, 알고리즘의 시간 복잡도나 공간 복잡도를 표현합니다. 'O'는 'Order of' 즉, '...의 차수'라는 의미로, 알고리즘이 입력 크기에 대해 얼마나 많은 계산이나 메모리가 필요한지를 나타내는 `상한선`을 표현합니다.

- `'n'`: 일반적으로 알고리즘의 `입력 크기`를 나타내는 변수입니다.

예를 들어 'O(1)'은 알고리즘의 실행 시간이 입력 크기와 관계없이 일정한 것을 뜻하고, 'O(n)'은 알고리즘의 실행 시간이 입력 크기에 선형적으로 비례하는 것을 나타내며, 'O(n²)'은 입력 크기의 제곱에 비례하여 실행 시간이 기하급수적으로 증가함을 의미합니다.

<br />

## 알고리즘의 복잡도 평가

알고리즘의 복잡도는 **시간 복잡도**와 **공간 복잡도** 두 가지 측면으로 평가힙니다.

1. `시간 복잡도 (Time Complexity)`: 알고리즘이 문제를 해결하는 데 걸리는 시간이 얼마나 되는지를 나타냅니다. 일반적으로 입력 크기에 따라 얼마나 많은 단계가 필요한지로 측정됩니다. 예를 들어 간단한 반복문은 입력 크기에 비례하는 '선형 시간 복잡도(O(n))'를 가지며, 중첩된 반복문은 '제곱 시간 복잡도(O(n²))'를 갖습니다.

2. `공간 복잡도 (Space Complexity)`: 알고리즘이 실행될 때 필요한 메모리 공간의 양을 뜻합니다. 예를 들어, 고정된 수의 변수만을 사용하는 알고리즘은 '상수 공간 복잡도(O(1))'를 가지며, 입력 크기에 비례하는 추가 메모리가 필요한 경우 '선형 공간 복잡도(O(n))'를 가집니다.

<br />