Нотація Ландау та аналіз алгоритмів з прикладами на Python

10 хв. читання

Майже для всіх комп'ютерних проблем існує декілька способів їх вирішити. Наприклад, для сортування масиву існує купа різних алгоритмів: сортування злиттям, бульбашкою, вставкою та інші. Всі ці алгоритми мають власні плюси та мінуси. Але постає питання: який алгоритм використовувати?

Для цього алгоритми потрібно аналізувати, а одним із мірил їх ефективності є швидкість виконання та використовувана память. Швидкість алгоритму описує нотація Ландау (її ще називають Big-O notation), сьогодні ми розглянемо саме її.

Чому важливо аналізувати алгоритми?

Давайте відразу розглянемо невеличкий приклад. Уявіть, що менеджер доручив двом програмістам розробити алгоритми для вирахування факторіалу від числа, введеного користувачем.

Алгоритм першого робітника виглядав так:

def fact(n):  
    product = 1
    for i in range(n):
        product = product * (i+1)
    return product

print (fact(5))  

Для розрахунку факторіалу він використав цикл. Другий робітник натомість використав рекурсію і написав ось такий код:

def fact2(n):  
    if n == 0:
        return 1
    else:
        return n * fact2(n-1)

print (fact2(5))  

Тепер менеджеру потрібно вирішити, який алгоритм використовувати. Для цього йому потрібно знайти складність обох алгоритмів. Один із способів це зробити — заміряти швидкість їх виконання на однакових вхідних даних.

В Jupyter notebook ви можете використовувати конструкцію %timeit для цього:

%timeit fact(50)
9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)  

З виводу ми бачимо, що алгоритму потрібно 9 мікросекунд (+/- 45 наносекунд).

%timeit fact2(50)
15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Натомість, другому алгоритму потрібно 15 мікросекунд (+/- 427 наносекунд).

Як бачите, перший алгоритм працює швидше. Звісно, різниця не така й велика, але при збільшенні вхідних даних вона буде тільки збільшуватися. Тим не менш, час — не така гарна метрика для виміру складності алгоритму, адже вона залежить від можливостей апаратного забезпечення. Нам потрібна більш об'єктивна метрика. І саме тут з'являється нотація Ландау.

Аналіз алгоритмів та Big-O

Нотація Ландау використовується для виміру складності алгоритму і відображає взаємозалежність між вхідними даними так кількістю кроків, потрібних для їх обробки. Вона записується як O(x), де x — кількість операцій, вхідні дані записуються як n.

В таблиці наведені найпопулярніші варіанти складності:

Назва Запис
Константа O(c)
Лінійна O(n)
Квадратична O(n^2)
Кубічна O(n^3)
Експонентна O(2^n)
Логарифмічна O(log(n))
Лінійно-логарифмічна O(nlog(n))

Давайте розглянемо деякі з ним на конкретних прикладах.

Константа складність O(c)

Якщо кількість операцій в алгоритмі не залежить від вхідних даних, така складність називається константною і записується як O(c), де c може бути будь-якою константою.

Давайте напишемо невеличку функцію, що буде повертати квадрат першого числа в списку та виводити його на екран:

def constant_algo(items):  
    result = items[0] * items[0]
    print (result)

constant_algo([4, 5, 6, 8])  

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

Якщо ви намалюєте діаграму, де х-ось буде відображати розмір вхідних даних, а у-ось — кількість кроків, ви отримаєте пряму лінію.

import matplotlib.pyplot as plt  
import numpy as np

x = [2, 4, 6, 8, 10, 12]

y = [2, 2, 2, 2, 2, 2]

plt.plot(x, y, 'b')  
plt.xlabel('Inputs')  
plt.ylabel('Steps')  
plt.title('Constant Complexity')  
plt.show()  

Графік

Лінійна складність O(n)

Лінійною називають таку складність коли кількість операцій лінійно-пропорційна до вхідних даних, записується як O(n).

Наприклад, програма, що виводить елементи списку в консоль:

def linear_algo(items):  
    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])  

Це алгоритм з лінійною складністю, адже кількість ітерацій така ж сама як розмір списку, який виводиться на екран.

Графік буде виглядати ось так:

import matplotlib.pyplot as plt  
import numpy as np

x = [2, 4, 6, 8, 10, 12]

y = [2, 4, 6, 8, 10, 12]

plt.plot(x, y, 'b')  
plt.xlabel('Inputs')  
plt.ylabel('Steps')  
plt.title('Linear Complexity')  
plt.show() 

Графік

Слід зауважити, що при великих обсягах вхідних даних, константи в складності алгоритму стають менш впливовими. Розглянемо такий скрипт:

def linear_algo(items):  
    for item in items:
        print(item)

    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

Тепер у нас є два цикли, що проходять по items, складність цього алгоритму складає O(2n), але при дійсно великих обсягах даних (автор приводить в приклад нескінченний обсяг даних, але ж ми живемо в реальному світі — прим. пер.), множник 2 стає неважливим, тому його ігнорують і записують складність як O(n).

Графік:

import matplotlib.pyplot as plt  
import numpy as np

x = [2, 4, 6, 8, 10, 12]

y = [4, 8, 12, 16, 20, 24]

plt.plot(x, y, 'b')  
plt.xlabel('Inputs')  
plt.ylabel('Steps')  
plt.title('Linear Complexity')  
plt.show()  

Графік

Квадратична складність O(n^2)

Квадратичною називають складність, за якої алгоритму потрібно n* n виконати операцій, вона записується як O(n^2). Розглянемо такий приклад:

def quadratic_algo(items):  
    for item in items:
        for item2 in items:
            print(item, ' ' ,item)

quadratic_algo([4, 5, 6, 8]) 

В коді вище є два вкладених цикла, тобто верхній цикл виконається n разів, а нижній, де саме й виконується єдина операція виводу на екран — n * n. Класичним прикладом алгоритму з квадратичною складністю є сортування бульбашкою, про яке ми згадували на початку.

Графік: Графік

А що робити з складними функціями?

Наші минулі приклади були досить простими, всього лише одна операція. А що робити з більш складними функціями? Розглянемо ось цей код:

def complex_algo(items):

    for i in range(5):
        print ("Python is awesome")

    for item in items:
        print(item)

    for item in items:
        print(item)

    print("Big O")
    print("Big O")
    print("Big O")

complex_algo([4, 5, 6, 8])  

Не дуже складно, але саме те що потрібно для нашого прикладу. Як рахувати складність таких функцій? Перш за все, потрібно розбити її на частини. Почнемо з цієї:

    for i in range(5):
        print ("Python is awesome")

Тут все просто: O(5), бо кількість ітерацій не залежить від вхідних даних.

for item in items:
        print(item)

Теж просто (особливо враховуючи те, що ми вже розглядали такий випадок) — O(n). Наступний цикл також буде O(n):

    for item in items:
        print(item)

І остання частина:

    print("Big O")
    print("Big O")
    print("Big O")

Вона дуже схожа на першу, лише без циклу. O(3).

Тепер, щоб знайти загальну складність, потрібно додати отримані значення:

O(5) + O(n) + O(n) + O(3)  

Трошки скоротимо це все:

O(8) + O(2n)

А тепер ще згадаємо, що константами ми можемо знехтувати (якщо в виразі фігурує n), отримуємо фінальне значення — O(n).

Найгірші випадки і випадки трошки краще

Зазвичай, коли вас питають про складність алгоритму, мають на увазі складність в найгіршому випадку. Але існують ще найкращий та середній випадки. Давайте розглянемо на прикладі функції пошуку елемента в списку:

def search_algo(num, items):  
    for item in items:
        if item == num:
            return True
        else:
            return False
nums = [2, 4, 6, 8, 10]

print(search_algo(2, nums))  

В даному прикладі ми шукаємо число 2 в списку, де воно знаходиться першим. В такому випадку складність алгоритму буде дорівнювати O(1). Але якщо ви будете шукати 10, то складність змінюється на O(n), що й буде найгіршим випадком.

Середня складність вираховується зазвичай на основі випадкового набору вхідних даних.

Трошки про память

Як я вже казав, кількість операцій — не єдине мірило ефективності алгоритму. Ще є така метрика, як кількість пам'яті, потрібна для роботи алгоритму. Розглянемо приклад:

def return_squares(n):  
    square_list = []
    return_squares
    for num in n:
        square_list.append(num * num)

    return square_list

nums = [2, 4, 6, 8, 10]  
print(return_squares(nums))  

Функція приймає список чисел та повертає список квадратів цих чисел. Для цього їй потрібно виділити память під новий список розміру n. Використовуючи нотацію Ландау, це виглядатиме як O(n).

Помітили помилку? Повідомте автору, для цього достатньо виділити текст з помилкою та натиснути Ctrl+Enter
Codeguida 5.8K
Приєднався: 8 місяців тому
Коментарі (0)

    Ще немає коментарів

Щоб залишити коментар необхідно авторизуватися.

Вхід / Реєстрація