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

Значи, бидејќи ние не може директно да се споредат runtimes на програми во секунди или минути, како да се споредуваат 2 различни алгоритми без оглед на нивната хардвер или софтвер на животната средина? Да се ​​создаде повеќе единствен начин на мерење на алгоритамски ефикасност, компјутерски научници и математичари смисли концепти за мерење на асимптотска комплексноста на програмата и нотација наречена "Биг Ohnotation" за опишување ова. Формалната дефиниција е дека на функцијата f (x) работи на редоследот на g (x) ако постои некој (x) вредноста, X ₀ и некои постојани, Ц, за кои f (x) е помала или еднаква на тоа постојано пати g (x) за сите x поголема од X ₀. 

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

Сега, замислете ако одлучите дека линеарно време, О (n), само не беше доволно брзо за вас? Можеби сте складирање на огромни жици, и не можат да си дозволат екстра време ќе биде потребно да напречни сите на нивните карактери броење еден-по-еден. Значи, ќе одлучите да пробате нешто различно. Што ако не ќе се случи веќе чување на бројот на карактери во низа, да речеме, во променлива наречена "Лен" на почетокот на програмата, дури и пред да се чуваат првиот карактер во вашиот стринг? Потоа, сите ќе треба да направите сега за да дознаете стринг должина, се провери што вредноста на променливата е. Вие нема да мора да се погледне на стринг себе на сите, и пристапуваат на вредноста на променлива како Лен се смета на асимптоматично постојана време операција, или О (1). Зошто е ова? Па, сетете се што асимптотска комплексност значи. Како функционира траење промени како на големината на вашите влезови расте? 

Велат дека се обидуваат да го добиете бројот на карактери во поголем стринг. Па, тоа не би било важно колку е голема да се направи низа, дури еден милион карактери, сите ќе треба да направите за да се најде должината на стрингот со овој пристап, е да се прочита на вредноста на променливата Лен, што веќе го направиле. Влезот должина, што е, на должината на стрингот сте се обидува да се најде, не влијае на сите колку брзо вашата програма работи. Овој дел од својата програма ќе се кандидира подеднакво брзо на еден карактер стринг и илјада карактер стринг, и тоа е причината зошто оваа програма ќе бидат наведени како трчање во постојан време во однос на влезот големина. 

Се разбира, постои одбивност. Вие трошат екстра мемориски простор на вашиот компјутер чување на променливата и дополнително време што ви е потребно да го направите вистинскиот складирање на променливата, но поентата сè уште стои, изнаоѓање колку долго вашиот стринг беше не зависи од должината на стрингот на сите. Значи, таа работи во О (1) или константа време. Ова секако не мора да значи дека вашиот код работи во 1 чекор, но без оглед колку чекори што е, ако тоа не се менува со големината на влезови, тоа е уште асимптоматично постојана кои ги застапуваме како О (1). 

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

Друга асимптотска комплексност е, логаритамска време, О (log n). Еден пример на алгоритам што работи ова брзо е класичен бинарни пребарување алгоритам, за изнаоѓање на елемент во веќе сортирана листа на елементи. 

Ако не знаете што бинарни пребарување не, Ќе го објаснам за што навистина брзо. Да речеме дека сте во потрага за број 3 во оваа низа од цели броеви. Тоа изгледа во средината елемент на низата и го прашува, "Дали елемент сакам поголем од еднаква на, или помалку од тоа?" Ако е еднаква, тогаш одлично. Го најде елементот, и ќе завршиш. Ако е поголема, тогаш знаете елементот мора да биде во десната страна на низата, а вие само може да се погледне дека во иднина, и ако е помала, тогаш знаете што треба да биде на левата страна. Овој процес е потоа се повторува со помала големина низа до точниот елемент се најде. 

Овој моќен алгоритам намалува низа големина на половина со секоја операција. Значи, да се најде на елемент во решат низа на големина 8, во повеќето (логирате ₂ 8), или 3 од овие операции, проверка на средината елемент, а потоа сечење на низата на половина ќе се бара, додека низа на големина 16 се (логирате ₂ 16), или 4 операции. Тоа е само 1 повеќе работа за двојно големина низа. Удвојување на големина на низата зголемува траење од само 1 парче на овој код. Повторно, проверка на средината елемент на листа, тогаш разделување. Значи, тоа се вели да работат во логаритамска време, О (log n). Но, чекај, ти што велиш, не ова зависи од тоа каде во листата на елементот што го барате е? Што ако првиот елемент да се погледне во се случува да биде вистинскиот? Потоа, таа само ја зема 1 операција, без разлика колку големи листата е. 

Па, тоа е зошто компјутерски научници имаат повеќе услови за асимптотска комплексноста кои се одразуваат на најдобар случај и најлошото перформансите на алгоритам. Повеќе правилно, горните и долните граници на траење. Во најдобар случај за бинарни пребарување, нашите елемент е право таму во средината, и ќе ја добиеш во постојан време, без разлика колку големи остатокот од низата е. Симболот се користи за ова е Ω. Значи, овој алгоритам се вели да се кандидира во Ω (1). Во најдобар случај, се наоѓа елементот брзо, без разлика колку големи низата е, но во најлош случај, тоа треба да се изврши (log n) Сплит проверки на низата да го најде вистинскиот елемент. Најлошото горните граници се наведени со големо "О" дека веќе знаете. Значи, тоа е О (log n), но Ω (1). 

А линеарно пребарување, пак, во која ви прошетка низ секој елемент од низата да се најде еден што сакате, е во најдобар Ω (1). Повторно, првиот елемент што го сакате. Значи, тоа не е важно колку е голема низа е. Во најлош случај, тоа е последниот елемент во низа. Значи, вие мора да одат низ сите n елементи во низа да го најдете, како ако сте биле во потрага за 3. Значи, таа работи во О (n) време затоа што тоа е пропорционален на бројот на елементи во низата. 

Уште еден симбол се користи е Θ. Ова може да се користи да се опише алгоритми, каде што најдобрите и најлошите случаи се исти. Ова е случај во низата должина алгоритми зборувавме претходно. Тоа е, ако го чувате во променлива пред ние чување на низа и да пристапите подоцна во постојан време. Без разлика на она што бројот ние сме чување во таа променлива, ние ќе треба да погледне во него. Најдобар случај е, ние се погледне во него и да се најде должината на стрингот. Значи Ω (1) или најдобар случај постојана време. Во најлош случај е, ние се погледне во него и да се најде должината на стрингот. Значи, О (1) или константа време во најлош случај. Така, од најдобар случај и најлош случај се исти, ова може да се каже да се кандидира во Θ (1) време. 

Во краток преглед, ние имаме добри начини да се причина за кодови ефикасност без да се знае нешто во врска со реалниот свет време тие се да се кандидира, кој е под влијание на многу надворешни фактори, вклучувајќи различни хардвер, софтвер, или спецификите на вашиот код. Исто така, тоа ни овозможува да размислиме и за тоа што ќе се случи кога големината на инпутите се зголемува. 

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

Тоа е асимптотска комплексност. Благодарам.