[Powered by Google Translate] Вероватно сте чули људи говоре о брзом и ефикасан алгоритам за извршавање свој посебан задатак, Али шта то значи за алгоритма да буде брзо или ефикасан? Па, то не говори о мерења у реалном времену, као секунди или минута. То је зато што рачунарски хардвер и софтвер варира драстично. Мој програм може покренути спорији од твог, јер ја то ради на старом рачунару, или зато што сам се деси да се игра онлине видео игре у исто време, што је празни све моје памћење, или ја можда ради мој програм кроз различите софтвера која комуницира са машином другачије на ниском нивоу. То је као поређење јабука и поморанџе. Само зато што је мој спорији рачунар траје дуже него твоја да врати одговор не значи да имате ефикаснији алгоритам. 

Дакле, пошто не можемо директно упоредити време рада програма у секунди или минута, Како се упореде 2 различите алгоритме без обзира на њихову хардвера или софтвера окружења? Да бисте направили више јединствен начин мерења ефикасности алгоритама, компјутерски научници и математичари су осмислили концепти за мерење асимптотско сложеност програма и нотација се зове "Биг Охнотатион ' за описивање ово. Формална дефиниција је да је функција ф (к) ради по налогу г (к) ако постоји неки (к) вредност, к ₀ и нека константа, Ц, за које ф (к) је мања или једнака та стална пута г (к) за све к веће од к ₀. 

Али, не плаши се далеко од формалног дефиницији. Шта то заправо значи у мање теоријском смислу? Па, то је у основи начин анализирања колико брзо неког програма рунтиме расте асимптотски. То је, како је величина ваших инпута повећава ка бесконачности, рецимо, ти сортирање низ величине у односу на 1000 низа величине 10. Како издржљивост вашег програма расте? На пример, замислите бројање карактера у низу најједноставнији начин  шетњом кроз цео стринг писмо по писмо и додавањем 1 до шалтера за сваког лика. Овај алгоритам се каже да раде у линеарном времену у односу на број знакова, 'Н' у низу. Укратко, ради у О (н). Зашто је ово? Па, користећи овај приступ, време потребно да пролазе целу ниску пропорционална броју карактера. Рачунајући број знакова у 20-знакова ће да се два пута док траје да бројим знакове у 10-знакова, јер морате да погледате све ликове а сваки лик има исту количину времена да погледам. Као што сте повећали број знакова, Рунтиме ће линеарно повећање са улазним дужине. 

Сада, замислите ако одлучите да је линеарно време, О (н), само није био довољно брз за тебе? Можда сте складиштење огромне жице, и не могу да приуште додатно време да би предузму да прођу све њихове карактере бројања један по један. Дакле, ви одлучите да пробате нешто друго. Шта ако би се десило да је већ меморишете број знакова у низу, рецимо, у променљивој под називом 'лен' рано у програму, пре него што чак чувају веома први карактер у свом стрингу? Затим, све што бих сада треба да урадите да бисте сазнали дужину ниске, се провери шта је вредност променљиве је. Не бих да погледам на самом низу на све, и приступу вредност променљиве као што лен се смета асимптотски константно време операције, или О (1). Зашто је ово? Па, сећам се шта асимптотска сложеност значи. Како се рунтиме промена као величина вашег улаза расте? 

Рецимо да су покушавали да добију број знакова у стрингу већи. Па, не би било битно колико сте направити стринг, чак милион знакова, Све ћеш морати да урадите да пронађу дужину стринга је са овим приступом, је да се прочита вредност променљиве лен, које сте већ направили. Улаз дужина, односно дужина низа који покушавате да пронађете не утиче на све како брзо ваш програм ради. Овај део вашег програма ће покренути једнако брзо на једном знакова и хиљаду карактера стринг, и то је разлог зашто би тај програм називају се ради у сталном времену у односу на улазну величину. 

Наравно, ту је недостатак. Можете провести додатни меморијски простор на рачунару складиштење променљиве и додатно време да вас води да стварно складиштење променљиве, али поента и даље стоји, проналажење колико дуго жица била не зависи од дужине стринга уопште. Дакле, ради у О (1) или константно време. То свакако не мора да значи да је ваш код ради у 1 кораку али без обзира на то колико корака је, ако то не мења са величином улаза, ипак је асимптотски цонстант које представљају као О (1). 

Као што вероватно можете погодити, постоји много различитих велике О време рада да се измери алгоритме са. О (н) ² алгоритми су асимптотски спорији од О (н) алгоритма. То је, као што је број елемената (н) расте, евентуално О (н) ² алгоритми ће бити потребно више времена од О (н) алгоритме за приказивање. То не значи О (н) алгоритми увек трчи брже од О (н) ² алгоритама, чак у истом окружењу, на истом хардверу. Можда за мале улазне величине,  је О (н) ² алгоритам може заправо раде брже, али, на крају, као улазну величину повећава према бесконачности, О (н) ² алгоритма рунтиме ће на крају засенити извршни од О (н) алгоритма. Баш као и било квадратне математичком функцијом  ће на крају престићи било линеарно функцију, без обзира колико је главе почети линеарну функцију почиње са. Ако радите са великим количинама података, алгоритми који раде у О (н) ² време заиста може завршити успорава свој програм, али за мале улазне величине, вероватно нећете ни приметити. 

Други Асимптотска комплексност је, логаритамска време О (лог н). Пример алгоритма који покреће ово брзо је класичан бинарна претрага алгоритам, проналажења елемента у вец сортиране листе елемената. 

Ако не знате шта бинарна претрага ради, Ја ћу то објаснити за вас заиста брзо. Рецимо да сте у потрази за број 3 У овом низу целих бројева. Изгледа по средњем елементу низа и пита: "Да ли је елемент желим већа, једнака или мања од овога?" Ако је исти, онда супер. Нашли сте елемент, и готови сте. Ако је већа, онда знате елемент мора да буде на десној страни низа, и можете само да погледате да у будућности, а ако је мања, онда знате да мора да буде на левој страни. Овај процес се онда понавља са мањим величине низа док се тачан елемент је пронађен. 

Овај моћни алгоритам смањује величину низа на пола са сваке операције. Дакле, да би пронашли елеменат у сортираном низу величине 8, највише (лог ₂ 8), или 3 ових операција, провере средњи елемент, а затим сече низ у полувремену ће бити потребно, док низ величине 16 узима (лог ₂ 16), или 4 операције. То је само још 1 операција за удвостручио величине низа. Удвостручује низа повећава рунтиме за само 1 комад овог законика. Опет, провера средњи елемент листе, а затим раздваја. Дакле, то је рекао да ради у логаритамском времену, О (лог н). Али, чекајте, ви кажете, не то зависи од тога где у листи елемент тражиш је? Шта ако је први елемент погледате деси да буде онај прави? Затим, потребно је само 1 рад, без обзира колика је листа. 

Па, то је зато компјутерски научници имају више термина за Асимптотска сложености која одражава најбољу случај и најгори случај наступи алгоритма. Више правилно, горња и доња границе на рунтиме. У најбољем случају за бинарном претрагом, наш елемент је тамо у средини, а ви га добити у сталном времену, без обзира колики је остатак низа се. Симбол се користи за ово је Ω. Дакле, овај алгоритам се каже да раде у Ω (1). У најбољем случају, она проналази брзо елемент, без обзира колика је низ је, али у најгорем случају, она мора да изврши (лог н) провере подељене низа да пронађете праву елемент. Најгори случај горњи границе упућују да са великим "О" које већ знате. Дакле, то је О (лог н), али Ω (1). 

Линеарно претраживање, насупрот томе, у којој ходате кроз сваки елемент низа да пронађете ону коју желите, је у најбољем Ω (1). Опет, први елемент који желите. Дакле, није битно колики је низ је. У најгорем случају, то је последњи елемент у низу. Дакле, морате ходати кроз све н елемената у низу да га пронађе, волео да сте у потрази за 3. Дакле, ради у О (н) времену јер је пропорционална броју елемената у низу. 

Још један симбол који се користи је Θ. Ово се може користити да опише алгоритме где је најбољи и најгори случајева су исти. То је случај у стринг дужине алгоритама смо причали раније. То јест, ако га чувати у променљивој пре чувамо ниску и приступили касније у сталном времену. Без обзира на број смо складиштење у тој променљивој, ми ћемо морати да га погледам. Најбољи случај је, гледамо на то и наћи дужину стринга. Дакле Ω (1) или најбољем случају константно време. Најгори случај је, гледамо га и наћи дужину стринга. Дакле, О (1) или стални пут у најгорем случају. Дакле, пошто најбољем случају и најгорих случајева су исти, то може да се каже да раде у Θ (1) време. 

Укратко, имамо добре начине да уразуми око кодова ефикасности не знајући ништа о стварном свету време они узимају да се покрене, која је погођена много спољних фактора, укључујући разликују хардвер, софтвер, или специфичности кода. Такође, омогућава нам да добро размишљају о томе шта ће се десити када је величина улаза повећава. 

Ако користите у О (н) ² алгоритма, или још горе, О (2 ⁿ) алгоритам, један од најбрже растућих врста, заиста ћете почети да приметити успоравање када почнете да радите са већим количинама података. 

То је асимптотско сложеност. Хвала.