Позначення Великої О (Big O) допомагає розробникам прогнозувати, як ефективність алгоритму змінюється в залежності від розміру вхідних даних, допомагаючи їм вибрати найефективніше рішення.
Зображення авторства
Чи маєте ви уявлення, на якому принципі побудована ефективність пошукової системи, яку ви любите? А як щодо позначення Великої О (Big O)?
Позначення Великої О дає змогу безпечно оцінити, як змінюється ефективність при збільшенні розміру даних, або, як кажуть інші, воно допомагає визначити масштабованість.
Сьогодні ми поглиблено розглянемо позначення Великої О, яке використовується для оптимізації ефективності алгоритмів і масштабованості.
Що таке Велика О (Big O)?
Позначення Великої О — це математична модель, яка дозволяє описати кількісні вирази того, як алгоритми реагують на зміни у розмірі вхідних даних. Воно також дає уявлення про час виконання або вимоги до пам'яті, і допомагає зрозуміти, чи є ваші алгоритми доступними. Це позначення ми використовуємо для оцінки поведінки алгоритму, коли розмір його входу збільшується, що часто передбачає його ефективність і масштабованість.
Припустимо, у вас є великий набір даних. Вибір правильного алгоритму сортування може бути складним, якщо ви не знайомі з позначенням Великої О. Позначення Великої О спрощує це рішення, надаючи легке для розуміння порівняння ефективності алгоритмів.
Щоб подивитися на це з більш людської точки зору — чи не хочете ви знати про найгірші умови руху, коли подорожуєте? Точно так само, позначення Великої О дає нам розуміння того, скільки алгоритмів нам потрібно знати, щоб зрозуміти їхні умови та який з них найкраще підходить для ваших потреб.
Сортування списку
При сортуванні чисел у списку методи, такі як Bubble Sort, Merge Sort та Quick Sort, виконують різну кількість операцій. Позначення Великої О дозволяє пояснити ці відмінності.
Наприклад, Bubble Sort має складність O(n2), що погіршує його ефективність при збільшенні розміру вхідних даних. Натомість складність Merge Sort — O(n log n), що робить його більш ефективним за QuickSort на більших наборах даних.
Просте пояснення
Ось основне:
- Велика О — це про найгірші сценарії (бо песимізм популярний у програмуванні)
- Це ваш помічник при виборі ідеального алгоритму
- Без цього ви програмуєте з зав'язаними очима. І це не весело!
Пам'ятайте: у світі алгоритмів Велика О — це ваше кришталеве скло. Вона не передбачить номери лотереї, але точно врятує вас, коли ваші дані вирішать пережити сплеск росту!
Розуміння різних типів складності
Знання різних форм складності в алгоритмах є надзвичайно важливим. Ці типи описують, як алгоритм працює в залежності від розміру вхідних даних.
Почнемо з того, щоб описати, що ми маємо на увазі під складністю, а потім розглянемо приклади різних типів складності.
Постійний час — O(1): Телепортер
Складність постійного часу виникає, коли, незалежно від розміру вашого набору даних, ефективність алгоритму завжди однакова. Час виконання постійний (незалежно від того, маєте ви 10 чи 10000 елементів, час виконання залишатиметься тим самим).
Приклад з реального світу: Це як взяти пульт від телевізора. Чи є у вас п’ять або 500 пультів, знайти правильний займає однакову мить.
Подивімося на цього швидкого героя в дії:
# Швидкість алгоритмів
arr = [1, 2, 3, 4, 5]
element = arr[0] # БАЦ! Миттєвий результат!
print(element)
Ось результат.
Фууух! Ви бачили це? Це настільки швидко, що ви могли б просто моргнути і не помітити!
Логарифмічний час — O(log n): Ефективний бібліотекар
Складність логарифмічного часу означає, що алгоритм може значно покращити свою роботу при збільшенні вхідних даних. Це часто трапляється з алгоритмами поділу і завоювання.
Приклад з реального світу: Це схоже на гру "Вгадай число". Кожним здогадом ви скорочуєте свої можливості вдвічі.
1–100? Вгадай 50. Забагато? Тепер це 1–49. Розумно, правда?
Подивись на цього книголюба в коді:
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid # Книгу знайдено! 📚
elif arr[mid] < target:
low = mid + 1 # Шукаємо в правій частині
else:
high = mid - 1 # Шукаємо в лівій частині
return -1 # Книгу немає! Може, собака її з’їла?
# Давайте шукати книгу!
arr = [1, 3, 5, 7, 9]
index = binary_search(arr, 7) # O(log n) магія відбувається тут
print(index)
Ось результат.
Бачите? Ми шукали число 7, і бінарний пошук знайшов його на індексі 3! Наш розумний бібліотекар знайшов книгу на полиці три, не напружуючись!
Лінійний час — O(n): Конвеєр
Складність лінійного часу означає, що ефективність алгоритму збільшується пропорційно розміру вхідних даних. Коли ми подвоюємо кількість елементів, алгоритм не стає надто повільним (відносно лінійного часу), оскільки подвоєння розміру входу прямо пов’язано з подвоєнням часу виконання.
Приклад з реального світу: Це як рахувати овець, щоб заснути.
Наш алгоритм буде:
- Рахувати кожен крок раз без пропусків
- Підсумовувати числа в кінці
Давайте подивимося на цього лінійного героя в дії:
# Лічильник на конвеєрі
def sum_list(arr):
total = 0
for num in arr: # Привіт кожному числу!
total += num
return total
arr = [1, 2, 3, 4, 5]
total = sum_list(arr) # O(n) магія відбувається тут
print(total)
Ось результат.
Бачите? Наш герой привітав кожне число рівно один раз.
Лініаритмічний час — O(n log n): Розумний сортувальник
Ця складність часу називається лініаритмічною, коли лінійний компонент і логарифмічна складність часу поєднуються, що легко можна знайти в ефективних алгоритмах сортування. Іншими словами, ефективність алгоритму переходить в n log n.
Приклад з реального світу: Уявіть собі, що ви сортуєте колоду карт, розділяючи її навпіл, сортуєте кожну половину, а потім об’єднуєте. Це merge sort!
Подивіться на цього розумного сортувальника:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half) # Поділимо та завоюємо!
merge_sort(right_half) # Магія рекурсії
i = j = k = 0
# Об’єднуємо відсортовані половини
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
# Завершуємо з залишками
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# Давайте подивимося це в дії!
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr) # O(n log n) чаклунство
print(arr)
Ось результат.
Ось! Тут наш розумний сортувальник перетворив хаос на порядок з майстерністю досвідченого бібліотекаря. Він перетворює неупорядкований масив на впорядкований і показує силу алгоритмів O(n log n).
Квадратичний час — O(n²): Тщательна черепаха
І наостанок, зустрічайте нашого уважного друга. Це як перевіряти кожен елемент на відповідність кожному іншому. Ретельно? Так. Швидко? Ну…
Квадратична складність часу означає, що алгоритм виконує кілька кроків, пропорційних квадрату розміру входу. З іншого боку, якщо ви подвоїте 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] # Міняємо місцями!
# Давайте спустимося по спіралі!
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr) # O(n^2) повільно і вперто
print(arr)
Ось результат.
В цьому прикладі наша черепаха (функція bubble_sort) сортує масив, демонструючи простоту алгоритмів квадратичної складності часу. Це не швидко, тому вона не виграє в гонці, але свою роботу виконала!
Кубічний час — O(n³): Майстер куба
Складність кубічного часу означає, що функція працює пропорційно кубу деякого вхідного параметра. Це рідкісне явище і зазвичай зустрічається в алгоритмах, які потрібно виконувати через три вкладені цикли.
Приклад з реального світу: Це як організувати 3D книжкову полицю, де кожну книгу потрібно порівнювати з кожною іншою книгою на кожній полиці. Уф!
Давайте подивимося, як наш майстер куба маніпулює матрицями:
def matrix_multiplication(A, B):
result = [[0 for _ in range(len(B[0]))] for _ in range(len(A))]
for i in range(len(A)): # Перше вимірювання: Дія!
for j in range(len(B[0])): # Друге вимірювання: Ще дія!
for k in range(len(B)):# Третє вимірювання: Куб завершено!
result[i][j] += A[i][k] * B[k][j]
return result
# Давайте множити матриці!
A = [[1, 2], [3, 4]]
B = [[2, 0], [1, 2]]
result = matrix_multiplication(A, B) # O(n^3) магія куба
print(result)
Ось результат.
Ось! Наш майстер куба тільки-но перемножив матриці швидше, ніж ви можете сказати "тривимірні шахи"!
В нашому прикладі, порівнюючи всі можливі комбінації рядків та стовпців, "майстер куба", відповідальний за множення матриць (функція matrix_multiplication), чітко показує, чому цей алгоритм має кубічну складність часу.
"Хоча це стає значно складнішим, алгоритм все ж правильно обчислює результат множення матриць!
Експоненціальний час — O(2^n): Діва, що подвоюється
Експоненціальна складність часу означає, що подвоєння довжини входу збільшить продуктивність алгоритму вдвічі.
Приклад з реального світу: Ви коли-небудь грали в задачу "пшениця та шахівниця"? Подвоїти зерно пшениці на кожній клітинці, і на 64-й клітинці у вас буде більше пшениці, ніж є на Землі!
Подивіться на нашу діву, що танцює Фібоначчі:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2) # Подвоєна проблема!
# Давайте знайдемо число Фібоначчі!
n = 10
result = fibonacci(n) # O(2^n) експоненціальне вибухання
print(result)
Ось результат.
Наша діва, що подвоюється, щойно обчислила 10-е число Фібоначчі.
У цій версії наша "діва, що подвоюється" (функція Fibonacci) може ефективно обчислити 10-е число Фібоначчі, але коли мова йде про більші значення, такі як 50-те, час обчислення стає дуже високим, оскільки ви бачите експоненціальне збільшення кількості рекурсивних викликів.
Факторіальний час — O(n!): Вибух перестановок
І, наостанок, грандіозне завершення складності! Продуктивність факторіальної складності часу є найгіршою і зростає факторіально з розміром входу. Це рідкісне явище і зазвичай стосується алгоритмів, що обчислюють всі (тобто нескінченні) перестановки заданого набору входу.
Приклад з реального світу: Уявіть собі, що ви плануєте розсадку за столом на вечерю, де порядок важливий, і хочете спробувати КОЖНУ можливу комбінацію.
З десятьма гостями ви отримаєте 3,628,800 варіантів розташування!
Запустимо цей складний феєрверк:
from itertools import permutations
def generate_permutations(s):
return list(permutations(s)) # Наближається вибух!
# Давайте зробимо перестановки!
s = 'ABC'
result = generate_permutations(s) # O(n!) кабум!
print(result)
Ось результат.
Ось і все! Наш майстер перестановок надав нам всі можливі варіанти розташування 'ABC'. Спробуйте з 'ABCDEFGH', якщо хочете відчути дух пригод (і маєте кілька років в запасі)!
Практичні приклади та їх нотація Big O: де теорія зустрічається з реальністю!
Готові побачити, як Big O (Велике О) демонструє свою силу в реальному світі? Давайте заглянемо в деякі повсякденні ситуації програмування і розкриємо їх секретні ідентичності складності!
Приклад 1: Чемпіон в хованки — Пошук в списку
Сценарій: Ви граєте в хованки з числами. Чи зможете ви знайти 70 на цьому святі чисел?
def linear_search(arr, target):
for i in range(len(arr)): # Заглянемо під кожен камінь
if arr[i] == target:
return i # Знайдено!
return -1 # Олі-оллі-оксен-фрі!
arr = [10, 23, 45, 70, 11, 15]
index = linear_search(arr, 70) # O(n) - можливо, доведеться перевірити кожне сховище
print(index)
Ось результат.
Вердикт Big O (Велике О): O(n) — У найгіршому випадку наш шукач перевіряє кожне число. Чим більше чисел, тим довший пошук!
Приклад 2: Чемпіон важкої ваги — Пошук найбільшого числа
Сценарій: Ви організовуєте конкурс на "Найбільше число". Хто стане чемпіоном?
def find_max(arr):
max_val = arr[0] # Поточний чемпіон
for num in arr: # Нехай почнеться змагання!
if num > max_val:
max_val = num # Новий чемпіон!
return max_val
arr = [10, 23, 45, 70, 11, 15]
max_value = find_max(arr) # O(n) - кожне число отримує шанс стати чемпіоном
print(max_value)
Ось результат.
Вердикт Big O (Велике О): O(n) — Ми даємо кожному числу шанс стати чемпіоном. Більше чисел — більше суперників!
Приклад 3: Matchmaker (Світчмейкер) — Об'єднання відсортованих списків
Сценарій: Ви виступаєте в ролі сватів для двох груп відсортованих чисел. Давайте створимо числову гармонію!
def merge_sorted_lists(list1, list2):
sorted_list = []
i = j = 0
while i < len(list1) and j < len(list2):
if list1[i] < list2[j]:
sorted_list.append(list1[i])
i += 1
else:
sorted_list.append(list2[j])
j += 1
sorted_list.extend(list1[i:])
sorted_list.extend(list2[j:])
return sorted_list
list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged_list = merge_sorted_lists(list1, list2) # O(n + m) - сватівство на кожне число в обох списках
print(merged_list)
Ось результат.
Вердикт Big O (Велике О): O(n + m) — Ми по черзі шукаємо пару для кожного числа в обох списках. Більше чисел — більше сватів!
Приклад 4: Множник — Обчислення факторіалу
Сценарій: Ви — майстер множення! Як швидко ви можете обчислити 5!?
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1) # Багато множень!
n = 5
result = factorial(n) # O(n) - множимо n разів
print(result)
Ось результат.
Вердикт Big O (Велике О): O(n) — Ми множимо n разів. Більші числа — більше множень!
Приклад 5: Flip (Перевертання) матриці — Транспонування матриці
Сценарій: Ви — акробат з матриць, перевертаючи рядки в стовпці. Це йога для двовимірних масивів!
def transpose_matrix(matrix):
transposed = []
for i in range(len(matrix[0])): # Для кожного стовпця...
transposed_row = []
for row in matrix: # ...беремо з кожного рядка
transposed_row.append(row[i])
transposed.append(transposed_row)
return transposed
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
transposed = transpose_matrix(matrix) # O(n * m) - перевертаємо матрицю!
print(transposed)
Ось результат.
Вердикт Big O (Велике О): O(n * m) — Ми відвідуємо кожен елемент лише один раз. Більша матриця — більше йога поз!
Мозковий виклик: Якщо ці алгоритми змагались би у гонці, який виграв би з малим входом? А як щодо величезного входу? Чи зміниться переможець?
Ось і все, друзі! Нотація Big O (Велике О) в дії, від хованок до йоги для матриць. Пам'ятайте, у світі алгоритмів важливо не лише виконати задачу — важливо зробити це зі стилем (і ефективністю)!
Реальні приклади алгоритмічних задач
Якщо ви ще не знаєте, ми останнім часом публікували близько 70 алгоритмічних задач на нашій платформі. Давайте розглянемо кілька з них разом.
Реверс літер, збереження слів
Напишіть функцію для реверсування літер, зберігаючи порядок слів.
Посилання на задачу: https://platform.stratascratch.com/algorithms/10415-reverse-letters-preserve-words
У цій задачі компанія Deloitte попросила нас написати функцію, яка реверсує літери, зберігаючи порядок слів. Ось кроки, якими ми можемо вирішити цю задачу:
- Розбити вхідний рядок на слова
- Реверсувати кожне слово
- Об'єднати реверсовані слова в єдиний рядок
- Повернути результат
Ось код для цього.
def reverse_letters(input_string):
words = input_string.split()
reversed_words = [word[::-1] for word in words]
output_string = ' '.join(reversed_words)
return output_string
Ось тестові випадки.
"The quick brown fox jumps over the lazy dog"
Ось результат.
Спільні елементи з повторюваними значеннями
Знайти спільні елементи в 2 заданих списках і повернути всі аспекти, навіть якщо вони повторюються.
Посилання на задачу:
https://platform.stratascratch.com/algorithms/10410-common-elements-with-repeated-values
У цій задачі компанія Amazon попросила нас знайти спільні елементи в 2 заданих списках і повернути всі аспекти, навіть якщо вони повторюються. Давайте розглянемо кроки для вирішення цієї задачі.
- Видобути списки з вхідного словника
- Підрахувати елементи в кожному списку
- Визначити спільні елементи
- Згенерувати результат у вигляді списку
5.
Повернути результат
Давайте подивимось на код.
def common_elements(input):
list1 = input["list1"]
list2 = input["list2"]
counter1 = {}
counter2 = {}
for item in list1:
if item in counter1:
counter1[item] += 1
else:
counter1[item] = 1
for item in list2:
if item in counter2:
counter2[item] += 1
else:
counter2[item] = 1
common = {}
for key in counter1:
if key in counter2:
common[key] = min(counter1[key], counter2[key])
result = []
for key, count in common.items():
result.extend([key] * count)
return result
Ось тестові випадки.
{"list1": [1, 2, 2, 3, 4], "list2": [2, 2, 3, 3, 4, 4]}
Ось результат.
Листок для нотації Big O (Великого О)
Висновок
У цій статті ми розглянули різні типи алгоритмів з нотацією Big O (Велике О) за допомогою багатьох прикладів.
Практика покращить ваші навички! Практикуючи, ви не тільки покращите свої навички в алгоритмах, але й підготуєтесь до інтерв'ю!
Спочатку опубліковано на https://www.stratascratch.com.
Перекладено з: What is Big O Notation? (+ Cheat Sheet)