Алгоритми

Поняття складності алгоритмів

Складність алгоритмів вимірюється в термінах часу та простору, які вони споживають. Найчастіше використовуються такі нотації:

Часова складність (Time Complexity)

Часова складність вимірює, як змінюється час виконання алгоритму в залежності від розміру вхідних даних. Основні нотації:

• O(1): Константна складність - час виконання не залежить від розміру вхідних даних.
• O(n): Лінійна складність - час виконання зростає лінійно з розміром вхідних даних.
• O(n^2): Квадратична складність - час виконання зростає пропорційно квадрату розміру вхідних даних.
• O(log n): Логарифмічна складність - час виконання зростає логарифмічно з розміром вхідних даних.
• O(n log n): Лінійно-логарифмічна складність - час виконання зростає пропорційно n log n.

Просторова складність (Space Complexity)

Просторова складність вимірює, скільки пам'яті потребує алгоритм в залежності від розміру вхідних даних. Основні нотації:

• O(1): Константна складність - алгоритм використовує постійну кількість пам'яті.
• O(n): Лінійна складність - алгоритм використовує пам'ять, пропорційну розміру вхідних даних.

Діаграма часової складності

Сортування бульбашкою

Алгоритм сортування бульбашкою порівнює сусідні елементи і міняє їх місцями, якщо вони в неправильному порядку. Це повторюється до тих пір, поки список не буде відсортований.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers)
print(sorted_numbers)
# [11, 12, 22, 25, 34, 64, 90]

Сортування вибіркою

Алгоритм сортування вибіркою знаходить мінімальний елемент з невідсортованої частини списку і міняє його місцями з першим елементом цієї частини. Це повторюється для всіх елементів списку.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

numbers = [64, 25, 12, 22, 11]
sorted_numbers = selection_sort(numbers)
print(sorted_numbers)
# [11, 12, 22, 25, 64]

Бінарний пошук

Алгоритм бінарного пошуку використовується для пошуку елемента в відсортованому списку. Він працює шляхом порівняння середнього елемента з шуканим значенням і рекурсивного пошуку в відповідній половині списку.

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

numbers = [11, 12, 22, 25, 34, 64, 90]
result = binary_search(numbers, 25)
print(result)
# 3