Big O Analysis — це техніка для аналізу та ранжування ефективності алгоритмів.
Це дозволяє вибрати найбільш ефективні та масштабовані алгоритми. Ця стаття є шпаргалкою Big O, яка пояснює все, що вам потрібно знати про нотацію Big O.
Що таке Big O Analysis?
Big O Analysis — це техніка для аналізу того, наскільки добре алгоритми масштабуються. Зокрема, ми запитуємо, наскільки ефективним є алгоритм із збільшенням розміру вхідних даних.
Ефективність — це те, наскільки добре використовуються системні ресурси під час отримання результату. Ресурси, про які ми в першу чергу стурбовані, це час і пам’ять.
Тому, виконуючи Big O Analysis, ми задаємо такі запитання:
Відповіддю на перше питання є просторова складність алгоритму, а на друге – його часова складність. Ми використовуємо спеціальну нотацію під назвою Big O Notation, щоб висловити відповіді на обидва запитання. Це буде розглянуто далі в Big O Cheat Sheet.
передумови
Перш ніж рухатися вперед, я повинен сказати, що щоб максимально використати цю шпаргалку Big O, вам потрібно трохи зрозуміти алгебру. Крім того, оскільки я буду наводити приклади Python, також корисно трохи зрозуміти Python. Поглиблене розуміння непотрібне, оскільки ви не будете писати код.
Як виконати аналіз Big O
У цьому розділі ми розповімо, як виконати аналіз Big O.
Виконуючи Big O Complexity Analysis, важливо пам’ятати, що продуктивність алгоритму залежить від того, як структуровано вхідні дані.
Наприклад, алгоритми сортування працюють найшвидше, коли дані в списку вже відсортовано в правильному порядку. Це найкращий сценарій для продуктивності алгоритму. З іншого боку, ті самі алгоритми сортування працюють найповільніше, коли дані структуровані у зворотному порядку. Це найгірший сценарій.
Виконуючи Big O Analysis, ми розглядаємо лише найгірший сценарій.
Аналіз складності простору
Давайте почнемо цю Big O Cheat Sheet з того, як виконати аналіз складності простору. Ми хочемо розглянути, як додаткова пам’ять, яку використовує алгоритм, масштабується, коли вхідні дані стають все більшими і більшими.
Наприклад, наведена нижче функція використовує рекурсію для циклу від n до нуля. Він має просторову складність, прямо пропорційну n. Це тому, що зі збільшенням n зростає і кількість викликів функцій у стеку викликів. Отже, він має просторову складність O(n).
def loop_recursively(n):
if n == -1:
return
else:
print(n)
loop_recursively(n - 1)
Однак краща реалізація виглядала б так:
def loop_normally(n):
count = n
while count >= 0:
print(count)
count =- 1
У наведеному вище алгоритмі ми створюємо лише одну додаткову змінну та використовуємо її для циклу. Якби n ставало все більшим і більшим, ми все одно використовували б лише одну додаткову змінну. Таким чином, алгоритм має постійну просторову складність, позначену символом «O(1)».
Порівнюючи просторову складність двох наведених вище алгоритмів, ми дійшли висновку, що цикл while був ефективнішим, ніж рекурсія. Це головна мета Big O Analysis: проаналізувати, як змінюються алгоритми, коли ми запускаємо їх із більшими вхідними даними.
Аналіз складності часу
Виконуючи аналіз складності часу, нас не хвилює зростання загального часу, який витрачає алгоритм. Радше нас турбує зростання обчислювальних кроків. Це тому, що фактичний час залежить від багатьох системних і випадкових факторів, які важко врахувати. Отже, ми відстежуємо лише зростання обчислювальних кроків і припускаємо, що кожен крок рівний.
Щоб допомогти продемонструвати аналіз складності часу, розглянемо такий приклад:
Припустімо, що у нас є список користувачів, де кожен користувач має ідентифікатор та ім’я. Наше завдання полягає в тому, щоб реалізувати функцію, яка повертає ім’я користувача, коли йому надається ідентифікатор. Ось як ми можемо це зробити:
users = [
{'id': 0, 'name': 'Alice'},
{'id': 1, 'name': 'Bob'},
{'id': 2, 'name': 'Charlie'},
]
def get_username(id, users):
for user in users:
if user['id'] == id:
return user['name']
return 'User not found'
get_username(1, users)
Маючи список користувачів, наш алгоритм перебирає весь масив користувачів, щоб знайти користувача з правильним ідентифікатором. Коли ми маємо 3 користувачів, алгоритм виконує 3 ітерації. Коли ми маємо 10, він виконує 10.
Тому кількість кроків лінійно і прямо пропорційна кількості користувачів. Отже, наш алгоритм має лінійну часову складність. Однак ми можемо вдосконалити наш алгоритм.
Припустімо, замість того, щоб зберігати користувачів у списку, ми зберігаємо їх у словнику. Тоді наш алгоритм пошуку користувача виглядатиме так:
users = {
'0': 'Alice',
'1': 'Bob',
'2': 'Charlie'
}
def get_username(id, users):
if id in users:
return users[id]
else:
return 'User not found'
get_username(1, users)
Припустімо, що з цим новим алгоритмом у нашому словнику є 3 користувача; ми б виконали кілька кроків, щоб отримати ім’я користувача. І припустимо, що у нас більше користувачів, скажімо десять. Щоб отримати користувача, ми виконаємо ту саму кількість кроків, що й раніше. Оскільки кількість користувачів зростає, кількість кроків для отримання імені користувача залишається постійною.
Тому цей новий алгоритм має постійну складність. Неважливо, скільки у нас користувачів; кількість виконаних обчислювальних кроків однакова.
Що таке нотація Big O?
У попередньому розділі ми обговорювали, як обчислити просторову та часову складність Big O для різних алгоритмів. Для опису складності ми використовували такі слова, як лінійний і постійний. Інший спосіб описати складність — використовувати нотацію Big O.
Нотація Big O — це спосіб представлення просторової або часової складності алгоритму. Нотація відносно проста; це O, за якою йдуть дужки. У круглих дужках ми пишемо функцію n для представлення конкретної складності.
Лінійна складність представлена n, тому ми б записали це як O(n) (читати як «O з n»). Постійна складність представлена 1, тому ми б записали її як O(1).
Є й інші складності, про які ми поговоримо в наступному розділі. Але загалом, щоб написати складний алгоритм, виконайте наступні кроки:
Результатом цього стає термін, який ми використовуємо в дужках.
приклад:
Розглянемо таку функцію Python:
users = [
'Alice',
'Bob',
'Charlie'
]
def print_users(users):
number_of_users = len(users)
print("Total number of users:", number_of_users)
for i in number_of_users:
print(i, end=': ')
print(user)
Тепер ми обчислимо Big O Time складність алгоритму.
Спочатку ми пишемо математичну функцію nf(n), щоб представити кількість кроків обчислення, які виконує алгоритм. Пам’ятайте, що n представляє розмір вхідних даних.
З нашого коду функція виконує два кроки: один для обчислення кількості користувачів, а інший для друку кількості користувачів. Потім для кожного користувача він виконує два кроки: один для друку індексу та другий для друку користувача.
Таким чином, функція, яка найкраще представляє кількість виконаних обчислювальних кроків, може бути записана як f(n) = 2 + 2n. Де n – кількість користувачів.
Переходячи до другого кроку, ми вибираємо найбільш домінуючий термін. 2n — лінійний термін, а 2 — постійний. Лінійний є більш домінуючим, ніж постійний, тому ми вибираємо 2n, лінійний член.
Отже, тепер наша функція f(n) = 2n.
Останнім кроком є усунення коефіцієнтів. У нашій функції ми маємо 2 як наш коефіцієнт. Тож ліквідуємо. І функція стає f(n) = n. Це термін, який ми використовуємо в дужках.
Таким чином, часова складність нашого алгоритму дорівнює O(n) або лінійній складності.
Різні великі O складності
В останньому розділі нашої шпаргалки Big O показано різні складності та відповідні графіки.
#1. Постійний
Постійна складність означає, що алгоритм використовує постійну кількість простору (під час виконання аналізу просторової складності) або постійну кількість кроків (під час виконання аналізу часової складності). Це найоптимальніша складність, оскільки алгоритм не потребує додаткового простору чи часу, коли вхідні дані зростають. Тому він дуже масштабований.
Постійна складність представлена як O(1). Однак не завжди можливо написати алгоритми, які працюють із постійною складністю.
#2. Логарифмічний
Логарифмічна складність представлена терміном O(log n). Важливо зауважити, що якщо основа логарифма не вказана в інформатиці, ми припускаємо, що вона дорівнює 2.
Таким чином, log n є log2n. Відомо, що логарифмічні функції спочатку швидко ростуть, а потім сповільнюються. Це означає, що вони масштабуються та ефективно працюють із дедалі більшими числами n.
#3. Лінійний
Для лінійних функцій, якщо незалежна змінна масштабується на коефіцієнт p. Залежна змінна масштабується з однаковим коефіцієнтом p.
Таким чином, функція з лінійною складністю зростає на той самий коефіцієнт, що й розмір вхідних даних. Якщо розмір вхідних даних подвоїться, кількість обчислювальних кроків або використання пам’яті також збільшиться. Лінійна складність представлена символом O(n).
#4. Лінійний
O (n * log n) представляє лінійні функції. Лінійні функції — це лінійна функція, помножена на логарифм. Таким чином, лінійна функція дає результати, дещо більші, ніж лінійні функції, коли log n більше за 1. Це тому, що n збільшується при множенні на число, більше за 1.
Log n є більшим за 1 для всіх значень n, більших за 2 (пам’ятайте, що log n дорівнює log2n). Отже, для будь-якого значення n, більшого за 2, лінійні функції менш масштабовані, ніж лінійні функції. З яких у більшості випадків n більше за 2. Таким чином, лінійні функції, як правило, менш масштабовані, ніж логарифмічні функції.
#5. Квадратичний
Квадратична складність представлена O(n2). Це означає, що якщо розмір вашого введення збільшується в 10 разів, кількість зроблених кроків або використаного простору збільшується в 102 рази або 100! Це не надто масштабно, і, як ви можете бачити з графіка, складність вибухає дуже швидко.
Квадратична складність виникає в алгоритмах, де ви циклюєте n разів, і для кожної ітерації ви повторюєте n разів знову, наприклад, у Bubble Sort. Хоча загалом це не ідеально, інколи у вас немає іншого вибору, окрім як реалізувати алгоритми квадратичної складності.
#6. Поліном
Алгоритм із поліноміальною складністю представлено O(np), де p — деяке постійне ціле число. P представляє порядок, у якому n підвищується.
Ця складність виникає, коли у вас є p кількість вкладених циклів. Різниця між поліноміальною складністю та квадратичною складністю полягає в тому, що квадратична складність має порядок 2, тоді як поліноміальна має будь-яке число, більше 2.
#7. Експоненціальний
Експоненціальна складність зростає навіть швидше, ніж поліноміальна. У математиці значенням за умовчанням експоненціальної функції є константа e (число Ейлера). Проте в інформатиці стандартним значенням експоненціальної функції є 2.
Експоненціальна складність представлена символом O(2n). Коли n дорівнює 0, 2n дорівнює 1. Але коли n збільшується до 5, 2n зростає до 32. Збільшення n на одиницю подвоїть попереднє число. Тому експоненціальні функції не дуже масштабовані.
#8. Факторіал
Факторна складність представлена символом O(n!). Ця функція також розвивається дуже швидко, тому її не можна масштабувати.
Висновок
У цій статті описано аналіз Big O та способи його розрахунку. Ми також обговорили різні складності та їх масштабованість.
Далі ви можете потренуватися в аналізі Big O на алгоритмі сортування Python.