Шта је Биг-О нотација?

Да ли сте се икада запитали зашто је програму који сте написали требало толико дуго да се покрене? Можда бисте желели да знате да ли можете да учините свој код ефикаснијим. Разумевање како се код изводи може ваш код довести на следећи ниво. Биг-О нотација је згодан алат за израчунавање ефикасности вашег кода.

Шта је Биг-О нотација?

Ознака Биг-О вам даје начин да израчунате колико ће времена требати за покретање вашег кода. Можете физички одредити колико времена треба да се изврши, али том методом је тешко ухватити мале временске разлике. На пример, време потребно између 20 и 50 линија кода је врло мало. Међутим, у великом програму се те неефикасности могу збрајати.

Ознака Биг-О броји колико корака алгоритам мора да изврши да би измерио своју ефикасност. Приближавање коду на овај начин може бити врло ефикасно ако требате подесити свој код да бисте повећали ефикасност. Биг-О нотација ће вам омогућити да мерите различите алгоритме бројем корака потребних за покретање и објективно упоређујете ефикасност алгоритама.

Како израчунавате Биг-О нотацију

Размотримо две функције које броје колико је појединачних чарапа у фиоци. Свака функција узима број парова чарапа и враћа број појединачних чарапа. Код је написан на Питхону, али то не утиче на то како бисмо рачунали број корака.

Алгоритам 1:

деф соцкЦоунтер (нумберОфПаирс):
индивидуалСоцкс = 0
за к у опсегу (нумберОфПаирс):
индивидуалСоцкс = индивидуалСоцкс + 2
вратите индивидуалСоцкс

Алгоритам 2:

деф соцкЦоунтер (нумберОфПаирс):
повраћај нумберОфПаирс * 2

Ово је глуп пример и требали бисте лако знати који је алгоритам ефикаснији. Али за вежбање, прођимо кроз сваку.

ПОВЕЗАН: Шта је функција у програмирању?

Шта је функција у програмирању?

Ако учите како да програмирате сопствени код, мораћете да разумете које су функције.

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

1. Променљивој индивидуалСоцкс додељује вредност нула.
2. Променљивој и додељује вредност један.
3. Поређује вредност и са нумберОфПаирс.
4. Додаје два на индивидуалСоцкс.
5. Повећава вредност индивидуалСоцкс додељује себи.
6. Повећава се за један.
7. Затим се петља назад кроз кораке 3 до 6 исти број пута као и (индивиуалСоцкс - 1).

Број корака које морамо обавити за један алгоритам може се изразити као:

4н + 2

Постоје четири корака која морамо обавити н пута. У овом случају, н би било једнако вредности нумберОфПаирс. Постоје и 2 корака која се завршавају једном.

За поређење, алгоритам 2 има само један корак. Вредност нумберОфПаирс множи се са два. Изразили бисмо то као:

1

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

Биг-О анализа

Генерално, када вас занима Биг-О нотација алгоритма, више вас занима укупна ефикасност, а мање анализа ситних зрна броја корака. Да бисмо поједноставили запис, можемо само навести величину ефикасности.

У горњим примерима алгоритам 2 би се изразио као један:

О (1)

Али алгоритам 1 би био поједностављен као:

На)

Овај брзи снимак нам говори како је ефикасност алгоритма један повезана са вредношћу н. Што је већи број, алгоритам ће морати да изврши више корака.

Линеар Цоде

Пошто не знамо вредност н, корисније је размислити о томе како вредност н утиче на количину кода који треба да се покрене. У алгоритму 1 можемо рећи да је веза линеарна. Ако уцртате број корака вс. вредност н добијате праву линију која иде горе.

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

Нису све везе тако једноставне као линеарни пример. Замислите да имате 2Д низ и желите да потражите вредност у низу. Можете створити алгоритам попут овог:

деф сеарцхФорВалуе (таргетВалуе, арраиСеарцхед):
фоундТаргет = Нетачно
за к у арраиСеарцхед:
за и у к:
иф (и == таргетВалуе):
фоундТаргет = Тачно
повратак фоундТаргет

У овом примеру, број корака зависи од броја низова у арраиСеарцхед и броја вредности у сваком низу. Дакле, поједностављени број корака би био н * н или н².

Овај однос је квадратни однос, што значи да број корака у нашем алгоритму експоненцијално расте са н. У нотацији Биг-О, написали бисте је као:

О (н²)

ПОВЕЗАН: Корисни алати за проверу, чишћење и оптимизацију ЦСС датотека

Логаритамски код

Иако постоји много других веза, последња веза коју ћемо размотрити је логаритамска веза. Да бисте освежили меморију, евиденција броја је вредност експонента потребна за достизање броја са основом. На пример:

лог 2 (8) = 3

Евиденција је једнака три, јер да је наша основа 2, била би нам потребна експоненцијална вредност 3 да бисмо дошли до броја 8.

Дакле, однос логаритамске функције је супротан експоненцијалном односу. Како се н повећава, за покретање алгоритма потребно је мање нових корака.

На први поглед ово делује контра-интуитивно. Како кораци алгоритма могу да расту спорије од н? Добар пример за то су бинарне претраге. Размотримо алгоритам за тражење броја у низу јединствених вредности.

• Започећемо са низом за претрагу који је ред од најмањег до највећег.
• Затим ћемо проверити вредност у средини низа.
• Ако је ваш број већи, изузећемо ниже бројеве у нашој претрази, а ако је број био мањи, изузећемо веће бројеве.
• Сада ћемо погледати средњи број преосталих бројева.
• Поново ћемо изузети половину бројева на основу тога да ли је наша циљна вредност виша или нижа од средње вредности.
• Наставићемо овај поступак док не пронађемо своју мету или утврдимо да је нема на списку.

Као што видите, будући да бинарне претраге уклањају половину могућих вредности при сваком пролазу, како н постаје све већи, ефекат на број проверавања низа једва утиче. Да бисмо ово изразили у Биг-О нотацији, написали бисмо:

О (лог (н))

Значај нотације Биг-О

Биг-О натион вам пружа брз и лак начин да комуницирате колико је алгоритам ефикасан. Ово олакшава одлучивање између различитих алгоритама. Ово може бити посебно корисно ако користите алгоритам из библиотеке и не морате нужно знати како код изгледа.

Када први пут научите да кодирате, почињете са линеарним функцијама. Као што видите из горњег графикона, то ће вас одвести далеко. Али како постајете искуснији и почињете да градите сложенији код, ефикасност почиње да постаје проблем. Разумевање начина квантификовања ефикасности кода даће вам алате који су вам потребни да бисте започели подешавање ефикасности и одмеравање предности и недостатака алгоритама.

10 најчешћих грешака у програмирању и кодирању

Грешке у кодирању могу довести до толико проблема. Ови савети ће вам помоћи да избегнете грешке у програмирању и одржи свој код смисленим.

О аутору