Algorithms
Алгоритми⚑
Рекурсія⚑
Рекурсія — це метод програмування, при якому функція викликає саму себе для розв’язання задачі. Зазвичай рекурсія використовується для задач, які можуть бути розділені на менші підзадачі аналогічної структури. Логіка рекурсивної функції, як правило, має дві гілки. Довга гілка викликає цю ж функцію з іншими параметрами, щоб накопичити результат. Коротка гілка встановлює критерій виходу з рекурсії.
Рекурсія, у деяких випадках, спрощує код та робить його декларативним. Рекурсія сприяє функціональному мисленню та уникненню побічних ефектів.
Рекурсія має базовий та рекурсивний випадок. Якщо рекурсивний алгоритм не матиме базового випадку, він буде виконуватися безкінечно, оскільки не буде умови, за якої потрібно повернути управління.
Як працює рекурсія - Кожен рекурсивний виклик створює нову копію функції в стеку викликів. - Рекурсія має базовий випадок (умову завершення), який запобігає нескінченним викликам.
def factorial(n):
if n == 0: # Base case: if n is 0, return 1
return 1
return n * factorial(n - 1) # Recursive case: multiply n by factorial of (n-1)
print(factorial(5)) # Output: 120
Недоліком рекурсії є те, що вона може спричиняти надмірне споживання пам'яті. Кожен рекурсивний виклик додає новий запис до стеку викликів, що може призвести до переповнення стеку (RecursionError у Python). Також відстеження рекурсивного коду може бути складнішим через велику кількість викликів, особливо для глибоких рекурсій.
Можливі способи оптимізації рекурсії - Мемоізація: Збереження результатів для вже обчислених підзадач. - Перехід до ітеративного підходу: Якщо можливо, можна переписати алгоритм у вигляді циклу.
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_optimized(n):
if n <= 1:
return n
return fibonacci_optimized(n - 1) + fibonacci_optimized(n - 2)
print(fibonacci_optimized(50)) # Output: 12586269025
Хвостова рекурсія⚑
Це особливий вид рекурсії, коли функція завершується викликом самої себе без додаткових операторів. Коли ця умова виконується, компілятор розгортає рекурсію в цикл з одним стек-фреймом, просто змінюючи локальні змінні від ітерації до ітерації.
Так, класичне визначення рекурсивного факторіала return N * fact(N - 1) не підтримує хвостову рекурсію, оскільки для кожного стек-фрейму доведеться зберігати поточне значення N.
Щоб зробити рекурсію хвостовою, додають параметри-акумулятори. Завдяки їм функція знає про свій поточний стан. Нехай параметр acc за замовчуванням дорівнює 1. Тоді запис з хвостовою рекурсією виглядатиме так:
Як можна оптимізувати хвостову рекурсію в Python⚑
class Recursion:
"""Can call other methods inside..."""
def __init__(self, func):
self.func = func
def __call__(self, *args, **kwargs):
result = self.func(*args, **kwargs)
while callable(result): result = result()
return result
def call(self, *args, **kwargs):
return lambda: self.func(*args, **kwargs)
@Recursion
def sum_natural(x, result=0):
if x == 0:
return result
else:
return sum_natural.call(x - 1, result + x)
print(sum_natural(1000000)) # Now even such call doesn't throw an error RuntimeError: maximum recursion depth exceeded
Links
O-велике при оцінці складності. Як і для чого використовується⚑
O-велике описує швидкість роботи алгоритму (не час).
Простий пошук⚑
O(n).
Бінарний пошук⚑
Бінарний пошук – це ефективний метод пошуку елемента у відсортованому масиві даних. Він заснований на принципі розділяй та володарюй і працює за логарифмічний час - O(log n).
Беремо середній елемент і перевіряємо, чи це той елемент, який ми шукаємо. Якщо ні і він менший, ніж той, який ми шукаємо - відкидаємо половину з меншими значеннями (якщо більше, то з більшими) і повторюємо, поки не знайдемо шуканий елемент.
def binary_search(list, item):
low = 0 # low and high keep track of which part of the list you'll search in.
high = len(list) - 1
while low <= high: # While you haven't narrowed it down to one element ...
mid = (low + high) // 2 # ... check the middle element
guess = list[mid] # Found the item.
if guess == item:
return mid
if guess > item: # The guess was too high.
high = mid - 1
else: # The guess was too low.
low = mid + 1
return None # Item doesn't exist
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # => 1
print(binary_search(my_list, -1)) # => None # We use None to indicate that the item wasn't found.
Фібоначчі⚑
Рекурсія
def fibonacci_recursive(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
n_terms = 10
fibonacci_terms = [fibonacci_recursive(i) for i in range(n_terms)]
print("Fibonacci sequence:", fibonacci_terms)
Цикл for
def fibonacci_loop(n):
sequence = []
a, b = 0, 1
for _ in range(n):
sequence.append(a)
a, b = b, a + b # Calculate the next by summing the previous two
return sequence
fibonacci_terms = fibonacci_loop(10)
print("Fibonacci sequence:", fibonacci_terms)
Лінійна складність сортування⚑
Лінійна складність сортування вказує на те, що час виконання сортування зростає лінійно відносно розміру вхідних даних. Іншими словами, якщо ми маємо список (або масив) з n елементів і сортуємо його за допомогою алгоритму з лінійною складністю, то час сортування збільшуватиметься приблизно в n раз зі збільшенням кількості елементів у списку.
Сортування бульбашкою⚑
Циклом for.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1): # Last i elements are already in place, so we don't need to check them
if arr[j] > arr[j+1]: # Swap if the element found is greater than the next element
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)
Циклом while.
def bubble_sort(arr):
n = len(arr)
sorted = False
while not sorted:
sorted = True
i = 0
while i < n-1:
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
sorted = False
i += 1
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)
Швидке сортування⚑
На першому етапі вибирають опорний елемент. Найчастіше його беруть із середини масиву. Потім послідовно порівнюють перший елемент масиву з останнім, другий з передостаннім і т. д. Якщо елемент зліва від опорного елемента більший за правий, вони міняються місцями. Коли доходять до опорного елемента, ітерація вважається завершеною.
Далі описаний вище алгоритм застосовується до двох підмасивів. Перший - від першого елемента до опорного елемента (не включно), другий - від опорного до останнього.
Рекурсивний спуск триває, доки довжини підмасивів не стануть рівними одиниці.
Складність швидкого сортування в середньому випадку дорівнює N * log(N).
O(n * log n) (середній та найкращий випадок), O(n^2) у найгіршому. Швидкість залежить від вибору опорного елемента - у більшості випадків виконується за середній час. Базовий випадок - у масиві 0 або 1 елемент, тоді він вже впорядкований.
Алгоритм: - Вибрати опорний елемент - Розділити масив на два підмасиви - з елементами менше та більше опорного - Рекурсивно застосовувати швидке сортування до двох підмасивів
def quicksort(array):
if len(array) < 2:
return array # base case, arrays with 0 or 1 element are already "sorted"
pivot = array[0] # recursive case
less = [i for i in array[1:] if i <= pivot] # sub-array of all the elements less than the pivot
greater = [i for i in array[1:] if i > pivot] # sub-array of all the elements greater than the pivot
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
Просте число⚑
def is_prime(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
def is_prime2(n):
if n < 2:
return False
for i in range(2, int(a ** 0.5 + 1)):
if n % i == 0:
return False
return True
def is_prime3(number):
if number <= 1:
return False
if number <= 3:
return True
if number % 2 == 0 or number % 3 == 0:
return False
i = 5
while i * i <= number: # Use optimized trial division: check divisors up to square root of the number
if number % i == 0 or number % (i + 2) == 0:
return False
i += 6 # all prime numbers are of the form 6n ± 1
return True
Пошук в ширину⚑
O(V + E), де V - кількість вершин, E - кількість ребер, працює з графами і допомагає відповісти на питання двох типів: - Чи існує шлях від вершини А до вершини Б? - Який найкоротший шлях від вершини А до вершини Б?
Алгоритм - Покласти вершину, з якої починається пошук, в початково порожню чергу. - Вилучити з початку черги вершину u та позначити її як розгорнуту. - Якщо вершина u є цільовою вершиною, то завершити пошук з результатом «успіх». - У протилежному випадку, в кінець черги додаються всі наступники вершини u, які ще не розгорнуті та не знаходяться в черзі. - Якщо черга порожня, то всі вершини зв'язаного графа були переглянуті, отже, цільову вершину неможливо досягнути з початкової; завершити пошук з результатом «невдача». - Повернутися до п. 2.
Використовується для знаходження найкоротшого шляху в незваженому графі.
Пошук в глибину⚑
Пошук у глибину - це алгоритм, що шукає по дереву (або графу) спочатку в глибину, починаючи з кореня.
Алгоритм йде по дереву, переходячи між рівнями лівими дочірніми вузлами, поки не дійде до самого низу. Завершивши прохід гілки, алгоритм повертається назад, переглядаючи праві дочірні вузли цієї гілки. Причому, якщо можливо, вибирає найлівіші з вузлів, розташованих праворуч від попереднього маршруту. Завершивши перегляд усієї гілки, алгоритм переходить до вузла, розташованого праворуч від кореня, і знову йде лівими дочірніми вузлами до самого дна. Останнім аналізується крайній правий вузол (розташований праворуч усіх своїх попередників).
Алгоритм оптимальний для пошуку по дереву, чия глибина перевищує ширину. Для роботи алгоритму використовується стек. Оскільки стек є LIFO-структурою, йому не потрібно відстежувати покажчики вузлів, тому споживається менше пам'яті, ніж у разі пошуку в ширину. Коли алгоритм не може далі йти ліворуч, він починає аналізувати стек.
Ефективність - O(|E|+ |V|), де E - кількість ребер (граней), V – кількість вершин.
Алгоритм Дейкстри⚑
Використовується для знаходження найлегшого шляху у зваженому графі. Працює лише у направлених ациклічних графах (DAG - Directed Acyclic Graph).
Складається з 4 кроків: - Знайти вершину з найменшою вагою. - Оновити вагу сусідів цієї вершини. - Повторювати, доки це не буде зроблено для всіх вершин. - Обчислити кінцевий шлях.
Не працює з від'ємними вагами - для графів з від'ємними вагами існує спеціальний алгоритм, відомий як алгоритм Беллмана-Форда.
Жадібні алгоритми⚑
Використовуються, коли обчислення точного рішення займає занадто багато часу або коли висока точність не є необхідною. Ефективність наближеного алгоритму оцінюється за такими критеріями: - швидкістю виконання - близькістю отриманого рішення до оптимального
Жадні алгоритми є хорошими не тільки тим, що їх зазвичай легко формулювати, але і тим, що простота зазвичай переходить у швидкість виконання.
Жадні алгоритми прагнуть до локальної оптимізації в розрахунку на те, що в кінцевому результаті буде досягнуто глобальний оптимум.
Жадні алгоритми легко реалізовуються та швидко виконуються, тому з них часто отримуються добрі наближені алгоритми.
Як впізнати NP-повну задачу⚑
Не існує простого способу зробити це, але існує ряд ознак: - алгоритм швидко працює при малій кількості елементів, але сильно уповільнюється при збільшенні їх кількості; - формулювання ~всі комбінації х~ часто вказує на NP-повноту задачі; - доводиться обчислювати всі можливі варіанти Х, оскільки задачу неможливо розбити на менші підзадачі? Така задача може виявитися NP-повною; - якщо в задачі зустрічається певна послідовність (наприклад, послідовність міст, як у задачі комівояжера) і задача не має простого рішення, вона може бути NP-повною; - якщо в задачі зустрічається певна множина (наприклад, множина радіостанцій) і задача не має простого рішення, вона може бути NP-повною; - чи можна переформулювати задачу в умовах задачі покриття множини або задачі комівояжера? У такому випадку ваша задача точно є NP-повною.
Для NP-повних задач не існує відомих швидких рішень. Якщо є NP-повна задача, то краще скористатися наближеним алгоритмом.
Динамічне програмування⚑
Застосовується для оптимізації певної характеристики, наприклад, покласти речі в рюкзак на найбільшу суму або знайти найдовшу підстроку у двох словах і так далі.
Працює лише в ситуаціях, коли задачу можна розбити на автономні підзадачі.
У кожному рішенні з області динамічного програмування будується таблиця (!). Значення комірок таблиці зазвичай відповідає оптимізованій характеристиці (ціна речей, їх важливість, кількість повторень літер і так далі).
Не існує єдиної формули для обчислення рішень методом динамічного програмування.
Алгоритм k найближчих сусідів⚑
Застосовується для класифікації та регресії. В ньому використовується перевірка k найближчих сусідів.
Класифікація - розподіл за категоріями.
Регресія - прогнозування результату (наприклад, у вигляді числа). Витягання ознаки називається перетворенням елемента (наприклад, фрукта чи користувача) в список чисел, які можна використовувати для порівняння. Якісний вибір ознак дуже важливий. Використовується в машинному навчанні, побудові рекомендаційних систем, прогнозуванні тощо.
Для обчислення відстані до сусіда використовується формула Піфагора (sqrt((x1 - x2)^2 + (y1 - y2)^2)) або метрика близькості косинусів. Метрика близькості косинусів не вимірює відстань між двома векторами, замість цього вона порівнює кути двох векторів.