Биг О анализа је техника за анализу и рангирање ефикасности алгоритама.
Ово вам омогућава да изаберете најефикасније и скалабилне алгоритме. Овај чланак је Биг О Цхеат Схеет који објашњава све што треба да знате о Биг О нотацији.
Преглед садржаја
Шта је Биг О анализа?
Биг О анализа је техника за анализу колико добро алгоритми скалирају. Конкретно, питамо колико је ефикасан алгоритам како се величина улаза повећава.
Ефикасност је колико се добро системски ресурси користе док се производи излаз. Ресурси који нас првенствено занимају су време и памћење.
Стога, када обављамо Биг О анализу, питања која постављамо су:
Одговор на прво питање је просторна сложеност алгоритма, док је одговор на друго његова временска сложеност. Користимо посебну нотацију која се зове Биг О нотација да бисмо изразили одговоре на оба питања. Ово ће бити покривено следеће у Великом О Цхеат Схеет-у.
Предуслови
Пре него што кренем напред, морам да кажем да да бисте максимално искористили ову Биг О Цхеат Схеет, морате да разумете мало алгебре. Поред тога, пошто ћу давати примере за Питхон, такође је корисно разумети мало Питхон-а. Детаљно разумевање је непотребно јер нећете писати никакав код.
Како извршити Биг О анализу
У овом одељку ћемо покрити како извршити Биг О анализу.
Када обављате анализу сложености великог броја, важно је запамтити да перформансе алгоритма зависе од тога како су структурирани улазни подаци.
На пример, алгоритми за сортирање раде најбрже када су подаци на листи већ сортирани у исправном редоследу. То је најбољи сценарио за перформансе алгоритма. С друге стране, исти алгоритми за сортирање су најспорији када су подаци структурирани обрнутим редоследом. То је најгори сценарио.
Када вршимо Биг О анализу, разматрамо само најгори сценарио.
Анализа сложености простора
Хајде да започнемо овај Биг О Цхеат Схеет покривајући како да извршимо анализу сложености простора. Желимо да размотримо како додатна меморија алгоритама користи размере како улаз постаје све већи и већи.
На пример, функција испод користи рекурзију за петљу од н до нуле. Има просторну сложеност која је директно пропорционална н. То је зато што како н расте, тако расте и број позива функција на стеку позива. Дакле, има комплексност простора од О(н).
def loop_recursively(n):
if n == -1:
return
else:
print(n)
loop_recursively(n - 1)
Међутим, боља имплементација би изгледала овако:
def loop_normally(n):
count = n
while count >= 0:
print(count)
count =- 1
У алгоритму изнад, креирамо само једну додатну променљиву и користимо је за петљу. Ако би н расло све веће и веће, и даље бисмо користили само једну додатну променљиву. Дакле, алгоритам има константну комплексност простора, означену симболом „О(1)“.
Упоређујући комплексност простора два горња алгоритма, закључили смо да је вхиле петља ефикаснија од рекурзије. То је главни циљ Биг О анализе: анализирати како се алгоритми мењају док их покрећемо са већим улазима.
Анализа временске сложености
Када вршимо анализу временске сложености, не брине нас раст укупног времена потребног алгоритму. Уместо тога, забринути смо због раста предузетих рачунских корака. То је зато што стварно време зависи од многих системских и случајних фактора које је тешко објаснити. Дакле, пратимо само раст рачунских корака и претпостављамо да је сваки корак једнак.
Да бисте помогли у демонстрацији анализе временске сложености, размотрите следећи пример:
Претпоставимо да имамо листу корисника где сваки корисник има ИД и име. Наш задатак је да имплементирамо функцију која враћа име корисника када се добије ИД. Ево како бисмо то могли да урадимо:
users = [
{'id': 0, 'name': 'Alice'},
{'id': 1, 'name': 'Bob'},
{'id': 2, 'name': 'Charlie'},
]
def get_username(id, users):
for user in users:
if user['id'] == id:
return user['name']
return 'User not found'
get_username(1, users)
Имајући у виду листу корисника, наш алгоритам пролази кроз читав низ корисника да би пронашао корисника са тачним ИД-ом. Када имамо 3 корисника, алгоритам изводи 3 итерације. Када имамо 10, он изводи 10.
Дакле, број корака је линеарно и директно пропорционалан броју корисника. Дакле, наш алгоритам има линеарну временску сложеност. Међутим, можемо побољшати наш алгоритам.
Претпоставимо да уместо да смештамо кориснике на листу, ми их складиштимо у речник. Тада би наш алгоритам за тражење корисника изгледао овако:
users = {
'0': 'Alice',
'1': 'Bob',
'2': 'Charlie'
}
def get_username(id, users):
if id in users:
return users[id]
else:
return 'User not found'
get_username(1, users)
Са овим новим алгоритмом, претпоставимо да имамо 3 корисника у нашем речнику; извршили бисмо неколико корака да бисмо добили корисничко име. А претпоставимо да имамо више корисника, рецимо десет. Извели бисмо исти број корака као и раније да бисмо добили корисника. Како број корисника расте, број корака за добијање корисничког имена остаје константан.
Стога, овај нови алгоритам има сталну сложеност. Није важно колико корисника имамо; број предузетих рачунских корака је исти.
Шта је Биг О нотација?
У претходном одељку смо разговарали о томе како израчунати просторну и временску комплексност Великог О за различите алгоритме. Користили смо речи као што су линеарни и константни да опишемо сложеност. Други начин да се опише сложеност је употреба Биг О нотације.
Биг О нотација је начин да се представи просторна или временска сложеност алгоритма. Запис је релативно једноставан; то је О праћено заградама. Унутар заграда пишемо функцију од н која представља одређену сложеност.
Линеарна сложеност је представљена са н, па бисмо је записали као О(н) (читај као „О од н“). Константна сложеност је представљена са 1, па бисмо је записали као О(1).
Постоји више сложености, о којима ћемо разговарати у следећем одељку. Али генерално, да бисте написали сложеност алгоритма, следите следеће кораке:
Резултат тога постаје термин који користимо унутар наших заграда.
Пример:
Размотрите следећу Питхон функцију:
users = [
'Alice',
'Bob',
'Charlie'
]
def print_users(users):
number_of_users = len(users)
print("Total number of users:", number_of_users)
for i in number_of_users:
print(i, end=': ')
print(user)
Сада ћемо израчунати комплексност алгоритма Биг О Тиме.
Прво пишемо математичку функцију од нф(н) која представља број рачунских корака које алгоритам предузима. Подсетимо се да н представља величину улаза.
Из нашег кода, функција обавља два корака: један за израчунавање броја корисника и други за штампање броја корисника. Затим за сваког корисника врши два корака: један за штампање индекса и један за штампање корисника.
Дакле, функција која најбоље представља број предузетих рачунских корака може се написати као ф(н) = 2 + 2н. Где је н број корисника.
Прелазећи на други корак, бирамо најдоминантнији термин. 2н је линеарни члан, а 2 је константан члан. Линеарно је више доминантно него константно, па бирамо 2н, линеарни члан.
Дакле, наша функција је сада ф(н) = 2н.
Последњи корак је елиминисање коефицијената. У нашој функцији имамо 2 као коефицијент. Зато га елиминишемо. И функција постаје ф(н) = н. То је термин који користимо између наших заграда.
Дакле, временска сложеност нашег алгоритма је О(н) или линеарна сложеност.
Различите велике О сложености
Последњи одељак у нашем Биг О Цхеат Схеет-у ће вам показати различите сложености и повезане графиконе.
#1. Константно
Константна сложеност значи да алгоритам користи константну количину простора (приликом анализе сложености простора) или константан број корака (приликом анализе временске сложености). Ово је најоптималнија сложеност јер алгоритам не треба додатни простор или време како унос расте. Стога је веома скалабилан.
Константна сложеност је представљена као О(1). Међутим, није увек могуће написати алгоритме који раде у сталној сложености.
#2. Логаритамски
Логаритамска сложеност је представљена појмом О(лог н). Важно је напоменути да ако база логаритма није наведена у рачунарству, претпостављамо да је 2.
Према томе, лог н је лог2н. Познато је да логаритамске функције у почетку брзо расту, а затим успоравају. То значи да се скалирају и ефикасно раде са све већим бројем н.
#3. Линеар
За линеарне функције, ако се независна променљива повећава за фактор п. Зависна варијабла се повећава за исти фактор п.
Дакле, функција са линеарном сложеношћу расте за исти фактор као и величина улаза. Ако се величина улаза удвостручи, повећаће се и број рачунарских корака или коришћење меморије. Линеарна сложеност је представљена симболом О(н).
#4. Линеаритамски
О (н * лог н) представља линеаритамске функције. Линеаритамске функције су линеарна функција помножена логаритамском функцијом. Према томе, линеаритамска функција даје резултате нешто веће од линеарних функција када је лог н већи од 1. То је зато што се н повећава када се помножи са бројем већим од 1.
Лог н је већи од 1 за све вредности н веће од 2 (запамтите, лог н је лог2н). Стога, за било коју вредност н већу од 2, линеаритамске функције су мање скалабилне од линеарних функција. Од којих је н у већини случајева веће од 2. Дакле, линеаритамске функције су генерално мање скалабилне од логаритамских функција.
#5. Квадратично
Квадратна сложеност је представљена са О(н2). То значи да ако се величина вашег уноса повећа за 10 пута, број предузетих корака или коришћени простор се повећава за 102 пута или 100! Ово није баш скалабилно, а као што можете видети из графикона, сложеност се веома брзо повећава.
Квадратна сложеност настаје у алгоритмима у којима петљате н пута, а за сваку итерацију поново петљате н пута, на пример, у Буббле Сортирању. Иако генерално није идеално, понекад немате друге опције осим да имплементирате алгоритме квадратне сложености.
#6. Полином
Алгоритам са полиномском сложеношћу је представљен са О(нп), где је п неки константни цео број. П представља редослед којим је н подигнуто.
Ова сложеност настаје када имате ап број угнежђених петљи. Разлика између сложености полинома и квадратне сложености је квадратна реда 2, док полином има било који број већи од 2.
#7. Експоненцијално
Експоненцијална сложеност расте чак и брже од полиномске сложености. У математици, подразумевана вредност за експоненцијалну функцију је константа е (Ојлеров број). У рачунарству, међутим, подразумевана вредност за експоненцијалну функцију је 2.
Експоненцијална сложеност је представљена симболом О(2н). Када је н 0, 2н је 1. Али када се н повећа на 5, 2н расте на 32. Повећање н за један ће удвостручити претходни број. Према томе, експоненцијалне функције нису веома скалабилне.
#8. Факторски
Факторска сложеност је представљена симболом О(н!). Ова функција такође расте веома брзо и стога није скалабилна.
Закључак
Овај чланак је покривао Биг О анализу и како је израчунати. Такође смо разговарали о различитим сложеностима и разговарали о њиховој скалабилности.
Затим, можда бисте желели да вежбате Биг О анализу на Питхон алгоритму за сортирање.