Позначення Big O - Просто пояснюється ілюстраціями та відео

Позначення Big O використовується для передачі швидкості роботи алгоритму. Це може бути важливим при оцінці чужих алгоритмів, а також при оцінці власних! У цій статті я розповім, що таке нотація Big O, і дам вам список найпоширеніших часів роботи алгоритмів, що її використовують.

Час роботи алгоритму зростає з різною швидкістю

У мого сина Юди багато іграшок. Насправді він придбав мільярд іграшок! Ви здивуєтесь, як швидко дитина може отримати стільки іграшок, якщо він перший онук по обидва боки сім'ї. ??

У будь-якому випадку, у Юди є проблема. Коли його друзі відвідують і хочуть пограти з конкретною іграшкою, знадобиться НАЗАВЖДИ, щоб знайти іграшку. Тож він хоче створити алгоритм пошуку, який допоможе йому якомога швидше знайти конкретну іграшку. Він намагається вибрати між двома різними алгоритмами пошуку: простим пошуком та двійковим пошуком. (Не хвилюйтеся, якщо ви не знайомі з цими алгоритмами.)

Обраний алгоритм повинен бути швидким і правильним. З одного боку, двійковий пошук пришвидшується. І у Джуди часто залишається лише близько 3 0 секунд, перш ніж його другові набридне шукати іграшку. З іншого боку, простий алгоритм пошуку легше писати, і менше шансів на появу помилок. Напевно, було б ніяково, якби його друг знайшов помилки у своєму коді! Щоб бути особливо обережним, Джуда вирішує приурочити обидва алгоритми списком із 100 іграшок.

Припустимо, що перевірка однієї іграшки займає 1 мілісекунду. За допомогою простого пошуку Джуда повинен перевірити 100 іграшок, тому на пошук потрібно 100 мс. З іншого боку, йому потрібно лише перевірити 7 іграшок за допомогою двійкового пошуку (log2 100 - приблизно 7, не хвилюйтеся, якщо ця математика заплутує, оскільки це не головне в цій статті), тож пошук займає 7 мс бігти. Але насправді у списку буде мільярд іграшок. Якщо це станеться, як довго триватиме простий пошук? Скільки часу займе двійковий пошук?

Тривалість простого пошуку проти двійкового пошуку зі списком із 100 елементів

Джуда проводить двійковий пошук з 1 мільярдом іграшок, і це займає 30 мс (log2 1 000 000 000 - це приблизно 30). “32 мс!” він думає. «Двійковий пошук приблизно в 15 разів швидший, ніж простий пошук, оскільки простий пошук зайняв 100 мс зі 100 елементами, а двійковий пошук - 7 мс. Тож простий пошук займе 30 × 15 = 450 мс, так? Досить 30 секунд, щоб моєму другові стало нудно ". Джуда вирішує піти на простий пошук. Це правильний вибір?

Ні. Виявляється, Джуда помилився і втратив друга на все життя. ? Тривалість простого пошуку з 1 мільярдом предметів складе 1 мільярд мс, це 11 днів! Проблема в тому, що час виконання двійкового пошуку та простого пошуку не зростає з однаковою швидкістю.

Час роботи зростає з дуже різною швидкістю! Зі збільшенням кількості елементів двійковий пошук займає трохи більше часу, але простий пошук займає набагато більше часу. Оскільки список чисел стає більшим, двійковий пошук раптом стає набагато швидшим, ніж простий пошук.

Отже, Юда помилявся, коли двійковий пошук завжди був у 15 разів швидшим, ніж простий пошук. Якщо є 1 мільярд іграшок, це швидше в 33 мільйони разів швидше.

Дуже важливо знати, як збільшується час роботи із збільшенням розміру списку. Ось де з’являється позначення Big O.

Позначення Big O говорить про те, наскільки швидким є алгоритм. Наприклад, припустимо, у вас є список розміру n . Для простого пошуку потрібно перевірити кожен елемент, тож це займе n операцій. Час роботи у позначенні Великого O - O ( n ).

Де секунди? Їх немає - Big O не повідомляє вам швидкість за лічені секунди. Позначення Big O дозволяє порівняти кількість операцій. Це говорить про те, як швидко зростає алгоритм.

Давайте зробимо ще один приклад. Для двійкового пошуку потрібні операції журналу n, щоб перевірити список розмірів n . Який час роботи в нотації Big O? Це O (журнал n ). Загалом, позначення Big O пишеться наступним чином.

Це говорить про кількість операцій, які виконує алгоритм. Це називається позначенням Великого О, тому що Ви ставите “велике О” перед кількістю операцій.

Big O встановлює найгірший час роботи

Припустимо, ви використовуєте простий пошук для пошуку користувача у вашій базі даних користувачів. Ви знаєте, що для простого пошуку потрібен час O ( n ), що означає, що в гіршому випадку вам алгоритму доведеться переглядати кожного користувача бази даних. У цьому випадку ви шукаєте користувача з ім'ям "aardvark213". Це перший користувач у списку. Отже, ваш алгоритм не повинен був розглядати кожен запис - він знайшов його з першої спроби. Чи займав алгоритм час O ( n )? Або це зайняло час O (1), тому що він знайшов людину з першої спроби?

Простий пошук все одно займає час O ( n ). У цьому випадку алгоритм миттєво знайшов те, що шукав. Це найкращий варіант. Але позначення Big O стосується найгіршого сценарію. Отже, ви можете сказати, що в гіршому випадку алгоритму доведеться один раз переглянути кожного користувача в базі даних. Це O ( n ) час. Це запевнення - ви знаєте, що простий пошук ніколи не буде повільнішим за O ( n ) час.

Деякі загальні часи роботи Big O

Ось п’ять великих пробігів, з якими ви зустрінетесь багато, відсортовані від найшвидшого до найповільнішого:

  • O (журнал n ), також відомий як час журналу. Приклад: двійковий пошук.
  • O ( n ), також відомий як лінійний час . Приклад: простий пошук.
  • O ( n * log n ). Приклад: Швидкий алгоритм сортування, наприклад, швидке сортування.
  • O ( n 2). Приклад: Алгоритм повільного сортування, як сортування виділення.
  • О ( н !). Приклад: Дійсно повільний алгоритм, як подорожній продавець.

Візуалізація різних періодів роботи Big O

Припустимо, ви малюєте сітку з 16 ящиків, і ви можете вибрати з 5 різних алгоритмів для цього. Якщо ви використовуєте перший алгоритм, вам знадобиться час O (log n ), щоб намалювати сітку. Ви можете робити 10 операцій в секунду. З часом O (log n ) вам знадобиться 4 операції, щоб намалювати сітку з 16 вікон (log 16 base 2 is 4). Отже, для малювання сітки вам знадобиться 0,4 секунди. Що робити, якщо вам доведеться намалювати 1024 коробки? Вам знадобиться ввести 1024 = 10 операцій, або 1 секунду, щоб намалювати сітку з 1024 ящиків. Ці числа використовують перший алгоритм.

Другий алгоритм повільніший: він вимагає часу O ( n ). Щоб намалювати 16 коробок, знадобиться 16 операцій, а 1024 - 1024 операції. Скільки часу це в секундах?

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

Є й інші періоди роботи, але це п’ять найпоширеніших.

Це спрощення. Насправді ви не можете акуратно перетворити час роботи Big O на ряд операцій, але це хороша оцінка.

Висновок

Ось основні виноси:

  • Швидкість алгоритму вимірюється не секундами, а збільшенням кількості операцій.
  • Натомість ми говоримо про те, як швидко збільшується час роботи алгоритму із збільшенням розміру вхідних даних.
  • Час роботи алгоритмів виражається в позначеннях Big O.
  • O (log n ) швидше, ніж O ( n ), але стає набагато швидше, оскільки список елементів, які ви шукаєте, зростає.

І ось відео, яке охоплює багато з того, що є в цій статті та багато іншого.

Сподіваюся, ця стаття принесла вам більше ясності щодо позначення Big O. Ця стаття заснована на уроці мого відеокурсу від Manning Publications під назвою «Алгоритми в русі». Курс заснований на дивовижній книзі Агіт Алгоритми Грокінга Адіта Бхаргави. Саме він намалював усі цікаві ілюстрації в цій статті.

Якщо ви найкраще навчаєтесь за допомогою книг, отримайте книгу! Якщо ви найкраще навчаєтесь через відео, розгляньте можливість придбання мого курсу. Ви можете отримати знижку на 39% з мого курсу, використовуючи код ' 39carnes '.