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

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

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





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

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



софтуер за организиране на файлове и папки

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





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

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

Алгоритъм 1:



def sockCounter(numberOfPairs):
individualSocks = 0
for x in range(numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks

Алгоритъм 2:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

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



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

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



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

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

4n + 2

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

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

1

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

Big-O анализ

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

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

O(1)

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

O(n)

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

Линеен код

Снимка: Ник Фледдерус/ Проект за съществителни

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

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

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

def searchForValue(targetValue, arraySearched):
foundTarget = False
for x in arraySearched:
for y in x:
if(y == targetValue):
foundTarget = True
return foundTarget

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

как да видите dpi на изображението

Снимка: Ник Фледдерус/ Проект за съществителни

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

O(n²)

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

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

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

log 2 (8) = 3

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

Снимка: Ник Фледдерус/ Проект за съществителни

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

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

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

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

O(log(n))

Значението на нотацията Big-O

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

как да добавите средства към портфейла ps4

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

Дял Дял Туит електронна поща 10 най -често срещани грешки при програмиране и кодиране

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

Прочетете Напред Свързани теми
  • Програмиране
  • Програмиране
За автора Дженифър Сийтън(21 статии са публикувани)

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

Още от Дженифър Сийтън

Абонирайте се за нашия бюлетин

Присъединете се към нашия бюлетин за технически съвети, рецензии, безплатни електронни книги и изключителни оферти!

Щракнете тук, за да се абонирате