Голямо O Обяснение, обяснено с примери

Нотацията Big O е начин да се опише скоростта или сложността на даден алгоритъм. Ако текущият ви проект изисква предварително дефиниран алгоритъм, важно е да разберете колко бърз или бавен е той в сравнение с други опции.

Какво е нотация Big O и как работи?

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

Това, което Big O нотация не ви казва, е скоростта на алгоритъма в секунди. Има твърде много фактори, които влияят на времето, необходимо на алгоритъма да се изпълни. Вместо това ще използвате обозначението Big O, за да сравнявате различни алгоритми по броя на извършените от тях операции.

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

Представете си, че сте учител с ученичка на име Джейн. Искате да намерите нейните записи, затова използвате прост алгоритъм за търсене, за да прегледате базата данни на вашия училищен окръг.

Знаете, че за обикновено търсене са необходими O (n) пъти. Това означава, че в най-лошия случай ще трябва да претърсите всеки отделен запис (представен с n), за да намерите Джейн.

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

Този алгоритъм отнема ли O (n) време? Или отнема време O (1), защото сте намерили записите на Jane от първия опит?

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

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

Да приемем, че отнема 1 милисекунда за проверка на всеки елемент в базата данни на училищния район.

С просто търсене, ако трябва да проверите 10 записа, ще отнеме 10 ms, за да стартирате. Но с двоичния алгоритъм за търсене трябва да проверите само 3 елемента, което отнема 3 ms, за да стартирате.

В повечето случаи списъкът или базата данни, които трябва да търсите, ще съдържа стотици или хиляди елементи.

Ако има 1 милиард елемента, използването на просто търсене ще отнеме до 1 милиард ms или 11 дни. От друга страна, използването на двоично търсене ще отнеме само 32 ms в най-лошия сценарий:

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

Ето защо знанието как се увеличава времето за работа по отношение на размера на списъка е толкова важно. И точно тук нотацията Big O е толкова полезна.

Нотацията Big O показва броя на операциите

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

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

Голяма O нотацияПримерен алгоритъм
O (log n)Двоично търсене
На)Лесно търсене
O (n * log n)Quicksort
O (n2)Сортиране на селекцията
На!)Пътуващ продавач

Сега знаете достатъчно, за да бъдете опасни с нотация Big O. Излезте там и започнете да сравнявате алгоритми.