Big O Notation - Просто обяснено с илюстрации и видео

Обозначението Big O се използва за комуникация колко бърз е алгоритъмът. Това може да е важно, когато оценявате алгоритмите на други хора и когато оценявате своите! В тази статия ще ви обясня какво е обозначението Big O и ще ви дам списък с най-често срещаните времена за работа на алгоритмите, които го използват.

Времето на работа на алгоритъма расте с различни темпове

Синът ми Джуда има много играчки. Всъщност той е придобил милиард играчки! Ще се изненадате колко бързо едно дете може да получи толкова много играчки, ако е първото внуче от двете страни на семейството. ??

Както и да е, Джуда има проблем. Когато приятелите му го посетят и искат да играят с определена играчка, може да отнеме ЗАВИНАГИ да я намери. Затова той иска да създаде алгоритъм за търсене, който да му помогне да намери конкретна играчка възможно най-бързо. Той се опитва да реши между два различни алгоритма за търсене: просто търсене и двоично търсене. (Не се притеснявайте, ако не сте запознати с тези алгоритми.)

Избраният алгоритъм трябва да бъде едновременно бърз и правилен. От една страна, бинарното търсене е по-бързо. А Джуда често има само около 3 0 секунди, преди приятелят му да се отегчи да търси играчка. От друга страна, прост алгоритъм за търсене е по-лесен за писане и има по-малък шанс за въвеждане на грешки. Със сигурност би било неудобно, ако приятелят му намери грешки в кода му! За да бъде особено внимателен, Джуда решава да зададе време и на двата алгоритма със списък от 100 играчки.

Да приемем, че отнема 1 милисекунда, за да проверите една играчка. С просто търсене Judah трябва да провери 100 играчки, така че търсенето отнема 100 ms. От друга страна, той трябва само да провери 7 играчки с двоично търсене (log2 100 е приблизително 7, не се притеснявайте, ако тази математика е объркваща, тъй като не е основната точка на тази статия), така че търсенето отнема 7 ms да бягам. Но наистина, списъкът ще има милиард играчки. Ако го направи, колко време ще отнеме простото търсене? Колко време ще отнеме двоичното търсене?

Работно време за просто търсене спрямо бинарно търсене, със списък от 100 елемента

Judah изпълнява двоично търсене с 1 милиард играчки и отнема 30 ms (log2 1,000,000,000 е приблизително 30). „32 мс!“ той си мисли. „Бинарното търсене е около 15 пъти по-бързо от обикновено търсене, тъй като простото търсене отне 100 ms със 100 елемента, а двоичното търсене отне 7 ms. Така че простото търсене ще отнеме 30 × 15 = 450 ms, нали? Доста по-малко от 30 секунди, необходими на приятеля ми да се отегчи. " Джуда решава да отиде с просто търсене. Това ли е правилният избор?

Не. Оказва се, че Джуда е сгрешил и е загубил приятел за цял живот. ? Времето за просто търсене с 1 милиард артикула ще бъде 1 милиард ms, което е 11 дни! Проблемът е, че времето за изпълнение на двоично търсене и просто търсене не нараства със същата скорост.

Времето за изпълнение растат с много различни скорости! Тъй като броят на елементите се увеличава, бинарното търсене отнема малко повече време за изпълнение, но простото търсене отнема много повече време. Тъй като списъкът с числа става по-голям, двоичното търсене изведнъж става много по-бързо от обикновено търсене.

Така че Джуда сгреши, че бинарното търсене винаги е било 15 пъти по-бързо от обикновено търсене. Ако има 1 милиард играчки, това е по-скоро 33 милиона пъти по-бързо.

Много е важно да знаете как се увеличава времето за работа с увеличаването на размера на списъка. Там се появява нотация Big O.

Нотацията Big O ви казва колко бърз е алгоритъмът. Да предположим например, че имате списък с размер n . Простото търсене трябва да провери всеки елемент, така че ще отнеме n операции. Времето за изпълнение в нотация на Big O е O ( n ).

Къде са секундите? Няма такива - Big O не ви казва скоростта за секунди. Нотацията Big O ви позволява да сравните броя на операциите. Той ви казва колко бързо расте алгоритъмът.

Нека направим още един пример. Двоичното търсене се нуждае от log n операции, за да провери списък с размер n . Какво е времето за работа в нотация на Big O? Това е O (log n ). По принцип обозначението Big O се пише по следния начин.

Това ви казва броя на операциите, които ще направи алгоритъм. Нарича се Big O notation, защото поставяте „голямо O“ пред броя на операциите.

Big O установява най-лошия случай

Да предположим, че използвате просто търсене, за да търсите потребител във вашата потребителска база данни. Знаете, че простото търсене отнема O ( n ) време, за да се изпълни, което означава, че в най-лошия случай вие ще трябва да прегледате всеки потребител в базата данни. В този случай търсите потребител с името „aardvark213“. Това е първият потребител в списъка. Така че вашият алгоритъм не трябваше да разглежда всеки запис - той го намери при първия опит. Отне ли алгоритъмът O ( n ) време? Или отнема време O (1), защото е намерил човека при първия опит?

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

Някои често срещани времена за изпълнение на Big O

Ето пет големи времена за изпълнение, които ще срещнете много, сортирани от най-бързо до най-бавно:

  • O (log n ), известен също като log log. Пример: двоично търсене.
  • 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.
  • O (log n ) е по-бърз от O ( n ), но става много по-бърз, тъй като списъкът с елементи, които търсите, нараства.

И ето видео, което обхваща много от това, което е в тази статия и не само.

Надявам се, че тази статия ви е донесла повече яснота относно нотацията Big O. Тази статия се основава на урок от моя видео курс от Manning Publications, наречен Algorithms in Motion. Курсът е базиран на невероятната книга Grokking Algorithms от Adit Bhargava. Той е този, който нарисува всички забавни илюстрации в тази статия.

Ако научите най-добре чрез книги, вземете книгата! Ако научите най-добре чрез видеоклипове, помислете за закупуване на моя курс. Можете да получите 39% отстъпка от курса ми, като използвате кода „ 39carnes “.