Какво е Big-O Notation?

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

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

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

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

Как изчислявате Big-O нотация

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

Алгоритъм 1:

def sockCounter (numberOfPairs):
individualSocks = 0
за x в обхват (numberOfPairs):
individualSocks = individualSocks + 2
върнете individualSocks

Алгоритъм 2:

def sockCounter (numberOfPairs):
връщане номерOfPairs * 2

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

СВЪРЗАНИ: Каква е функцията в програмирането?

Каква е функцията в програмирането?

Ако научавате как да програмирате свой собствен код, ще трябва да разберете какви са функциите.

Алгоритъм 1 има много стъпки:

1. Той присвоява стойност нула на променливата individualSocks.
2. Той присвоява стойност един на променливата i.
3. Сравнява стойността на i с numberOfPairs.
4. Той добавя две към individualSocks.
5. Той приписва увеличената стойност на individualSocks на себе си.
6. Той увеличава i с едно.
7. След това се връща обратно през стъпки 3 до 6 за същия брой пъти като (indiviualSocks - 1).

Броят стъпки, които трябва да извършим за един алгоритъм, може да бъде изразен като:

4n + 2

Има четири стъпки, които трябва да извършим n пъти. В този случай n би било равно на стойността на numberOfPairs. Има и 2 стъпки, които са изпълнени веднъж.

За сравнение, алгоритъм 2 има само една стъпка. Стойността на numberOfPairs се умножава по две. Бихме изразили това като:

1

Ако вече не беше очевидно, сега лесно можем да видим, че алгоритъм 2 е доста по-ефективен.

Big-O анализ

Като цяло, когато се интересувате от обозначението Big-O на даден алгоритъм, вие се интересувате повече от цялостната ефективност и по-малко от анализа на фините зърна на броя стъпки. За да опростим обозначението, можем просто да посочим величината на ефективността.

В примерите по-горе алгоритъм 2 ще бъде изразен като един:

O (1)

Но алгоритъм 1 ще бъде опростен като:

На)

Тази бърза снимка ни казва как ефективността на алгоритъм едно е свързана със стойността на n. Колкото по-голям е броят, толкова повече стъпки ще трябва да изпълни алгоритъмът.

Линеен код

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

Квадратичен код

Не всички взаимоотношения са толкова прости, колкото линейния пример. Представете си, че имате 2D масив и бихте искали да търсите стойност в масива. Можете да създадете алгоритъм като този:

def searchForValue (targetValue, arraySearched):
foundTarget = Невярно
за x в масив Търсено:
за y в x:
ако (y == targetValue):
foundTarget = Вярно
връщане foundTarget

В този пример броят на стъпките зависи от броя на масивите в arraySearched и броя на стойностите във всеки масив. И така, опростеният брой стъпки би бил n * n или n².

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

O (n²)

СВЪРЗАНИ: Полезни инструменти за проверка, почистване и оптимизиране на CSS файлове

Логаритмичен код

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

log 2 (8) = 3

Дневникът е равен на три, защото ако нашата база е 2, ще ни е необходима експонентна стойност 3, за да стигнем до числото 8.

И така, връзката на логаритмична функция е противоположна на експоненциална връзка. С нарастването на n се изискват по-малко нови стъпки за стартиране на алгоритъма.

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

• Ще започнем с масив за търсене, който е в ред от най-малкия до най-големия.
• След това ще проверим стойността в средата на масива.
• Ако вашият номер е по-голям, ние ще изключим по-ниските числа в нашето търсене, а ако броят е по-малък, ще изключим по-високите числа.
• Сега ще разгледаме средния брой на останалите числа.
• Отново ще изключим половината числа въз основа на това дали целевата ни стойност е по-висока или по-ниска от средната стойност.
• Ще продължим този процес, докато намерим нашата цел или не установим, че тя не е в списъка.

Както можете да видите, тъй като бинарните търсения елиминират половината от възможните стойности при всяко преминаване, тъй като n се увеличава, ефектът върху броя пъти, в които проверяваме масива, е едва засегнат. За да изразим това в Big-O нотация, бихме написали:

O (log (n))

Значението на Big-O Notation

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

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

10 най-често срещани грешки при програмирането и кодирането

Грешките при кодирането могат да доведат до толкова много проблеми. Тези съвети ще ви помогнат да избегнете грешки при програмирането и да запазите кода си смислен.

За автора