[Powered by Google Translate] Jūs droši vien esat dzirdējis cilvēkus runājam par ātru vai efektīva algoritma izpildei jūsu konkrēto uzdevumu, bet ko tieši tas nozīmē algoritmu, lai būtu ātri un efektīvi? Nu, tas nav runā par mērījumiem reālā laikā, piemēram sekundēs vai minūtēs. Tas ir tāpēc, datoru aparatūru un programmatūras krasi atšķiras. Mana programma varētu darboties lēnāk nekā jums, jo es skrienu to vecāku datoru, vai tāpēc es gadās būt spēlējot tiešsaistes video spēli tajā pašā laikā, kas ir hogging visu manu atmiņu, vai es varētu darboties savu programmu cauri dažādu programmatūru kas sazinās ar mašīnu savādāk zemā līmenī. Tas ir tāpat kā salīdzināt ābolus ar apelsīniem. Tikai tāpēc, ka mans lēnāka datora aizņem ilgāku kā jums dot atpakaļ atbildi nenozīmē, ka jums ir daudz efektīvāku algoritmu. 

Tātad, jo mēs nevaram tieši salīdzināt runtimes, programmu sekundēs vai minūtēs, kā mēs salīdzināt 2 dažādus algoritmus neatkarīgi no viņu aparatūras vai programmatūras vidē? Lai radītu vienotu iespējams izmērīt algoritmiskās efektivitāti, datorzinātnieku un matemātiķi ir izstrādājušas koncepcijas mērīšanas asimptotiskās sarežģītību programmas un pieraksta sauc par "Big Ohnotation" lai aprakstītu to. Formālā definīcija ir funkcija f (x) iet par kārtību g (x) ja pastāv zināma (x) vērtība, x ₀ un daži konstante, C, par kuru f (x) ir mazāks vai vienāds ar ka nemainīga reizes g (x) visiem x lielāks nekā x ₀. 

Bet vai nav bail prom ar formālās definīcijas. Ko tas patiesībā nozīmē mazāk teorētisko izteiksmē? Nu, tas būtībā veids analizējot cik ātri programma ir izpildlaika aug asimptotiski. Tas ir, jo no jūsu izejvielu izmērs palielinās virzienā bezgalībai, teiksim, jūs šķirošanas masīvs 1000 izmēra, salīdzinot ar masīvu 10 izmēra. Kā jūsu programmā izpildlaika augt? Piemēram, iedomājieties skaitīšana rakstzīmju virknē visvienkāršākais veids  ejot cauri visai string burtu pa vēstuli un pievienojot 1 līdz counter katram raksturs. Šis algoritms ir teikt palaist lineārā laika attiecībā uz zīmju skaitu, "N" virknē. Īsi sakot, tas darbojas O (n). Kāpēc tas tā ir? Nu, izmantojot šo pieeju, laiks, kas nepieciešams lai šķērsotu virtenei ir proporcionāls rakstzīmju skaitu. Saskaitot rakstzīmēm 20 rakstzīmju virkne gatavojas veikt divreiz tik ilgi, cik tas nepieciešams saskaitīt rakstzīmes 10 rakstzīmju virknes, jo jums ir apskatīt visas rakstzīmes un katrs simbols aizņem tikpat daudz laika, lai apskatīt. Kā jūs palielināt zīmju skaitu, izpildlaika palielinās lineāri ar ievades garuma. 

Tagad iedomājieties, ja jūs nolemjat, ka lineārā laika, O (N), vienkārši nav pietiekami ātri, lai jūs? Varbūt jūs uzglabātu milzīgu stīgas, un jūs nevarat atļauties papildu laiku, kas būtu nepieciešams lai šķērsotu visu to īpašību skaitīšanas vienu pa vienam. Tātad, esat nolēmis izmēģināt kaut ko atšķiras. Ko darīt, ja jūs varētu notikt jau glabāt zīmju skaitu virknē, teiksim, jo ​​mainīgo sauc "len" agri programmā, Pirms jūs pat glabājas ļoti pirmo rakstzīmi jūsu virknes? Tad viss jūs ir jādara tagad, lai uzzinātu stīgu garumu, ir jāpārbauda, ​​kāda ir mainīgā vērtība ir. Jums nebūtu jāskatās uz virkni pati vispār, un piekļūstot mainīgā vērtību, piemēram, len tiek uzskatīta asimptotiski nemainīgs laika darbību, vai O (1). Kāpēc tas tā ir? Nu, atceros, ko asimptotiskais sarežģītība nozīmē. Kā runtime izmaiņas, jo izmērs no jūsu ieejas aug? 

Say jūs mēģināt iegūt rakstzīmju skaitu lielāku virknē. Nu, tas nav svarīgi, cik liels jūs veicat virkni, pat miljons rakstzīmēm, visi jūs jādara, lai atrastu string garuma ar šo pieeju, ir nolasīt vērtību mainīgā len, kas jums jau veikti. Ieejas garums, tas ir, garums string jūs mēģināt atrast, neietekmē vispār, cik ātri jūsu programma darbojas. Šī jūsu programmas daļa varētu darboties tikpat strauji uz vienu rakstzīmju virkne un tūkstoš rakstzīmju virkne, un tāpēc šī programma būtu minēta kā darbojas pastāvīgu laiku attiecībā uz ieejas lielumu. 

Protams, tur ir trūkums. Jūs tērēt papildus atmiņas vietu datorā uzglabājot mainīgo un papildu laiks, kas jūs aizvedīs darīt faktisko uzglabāšanu mainīgo, bet punkts joprojām stāv, uzzināt, cik ilgi jūsu string bija nav atkarīga no garuma virknes vispār. Tātad, tas darbojas O (1) vai pastāvīgu laiku. Tas noteikti nav jāsaprot ka jūsu kods darbojas 1 solis, bet nav svarīgi, cik daudz soļus tas ir, ja tas nemaina ar izmēru ieguldījumiem, tas joprojām asimptotiski konstante, ko mēs pārstāvam, O (1). 

Kā jūs varat droši uzminēt, ir daudz dažādu Big O runtimes lai izmērītu algoritmus ar. O (n) ² algoritmi ir asimptotiski lēnāks nekā O (N) algoritmiem. Tas ir, kā to elementu skaits (n) aug, beidzot O (n) ² algoritmi vēl būs nepieciešams laiks kā O (n) algoritmus, lai palaistu. Tas nenozīmē, O (n) algoritmi vienmēr darboties ātrāk kā O (n) ² algoritmus, pat tajā pašā vidē, tajā pašā aparatūru. Varbūt mazajiem ieejas izmēriem,  O (n) ² algoritms tiešām strādāt ātrāk, bet, galu galā, kā ieejas lielumu palielina pret bezgalību, O (n) ² algoritms ir izpildlaika beidzot aizēnot runtime par O (n) algoritms. Tāpat kā jebkuru kvadrātvienādojums matemātisko funkciju  beidzot apsteigs jebkuru lineāro funkciju, Nav svarīgi, cik daudz no galvas sāk lineāru funkciju sākas ar. Ja jūs strādājat ar lielu datu apjomu, algoritmi, kas darbosies O (n) ² laiku tiešām var beigties palēninot savu programmu, bet mazajiem ieejas izmēriem, Jūs, iespējams, pat nepamanīsiet. 

Vēl asimptotiskās sarežģītība ir, logaritmiskā laiks, O (log n). Piemērs algoritmu, kas vada šo ātri ir klasisks bināro meklēšanas algoritmu, lai atrastu elements jau tā-sakārtoti sarakstā elementu. 

Ja jūs nezināt, ko binārā meklēšana dara, Es paskaidrošu to you tiešām ātri. Pieņemsim, ka jūs meklējat skaits 3 Šajā masīvs integers. Tas izskatās pēc vidējā elementu masīva un jautā: "Vai elements es gribu lielāka, vienāda vai mazāka par šo?" Ja tas ir vienāds, tad lieliski. Jūs atrast elementu, un jūs darīts. Ja tas ir lielāks, tad jūs zināt elements ir būt pareizajā pusē masīva, un jūs varat tikai apskatīt, ka nākotnē, un, ja tas ir mazāks, tad jūs zināt, tas ir jābūt kreisajā pusē. Šis process tiek atkārtots ar mazāku izmēra masīvs līdz pareizu elements ir atrasts. 

Šī jaudīga algoritms samazina masīva izmēru pusē ar katru darbību. Tātad, lai atrastu elementu sakārtoti masīvs 8 izmēra, augstākais (log ₂ 8), vai 3 no šīm operācijām, Pārbaudot vidējo elementu, tad griešanas masīvs pusē būs nepieciešama, tā 16 izmēra masīvs aizņem (log ₂ 16), vai 4 operācijas. Tas ir tikai vēl 1 operācija uz dubultojies izmēra masīvs. Divkāršojot masīva palielina izpildlaika tikai 1 rieciens šo kodu. Atkal, pārbaudot vidējo elementu sarakstu, tad sadalīšana. Tātad, tas teica darboties logaritmiskajā laikā, O (log n). Bet pagaidiet, jūs sakāt, nav tas atkarīgs no tā, kurā sarakstā elements jūs meklējat ir? Ko darīt, ja pirmais elements paskatās notiek, ir pareizais? Tad, tas aizņem tikai 1 darbību, Nav svarīgi, cik liels šis saraksts ir. 

Nu, tāpēc datorzinātnieku ir vairāk termini par asimptotiskās sarežģītību, kas atspoguļo labāko-lietu un sliktākajā gadījumā izrādes algoritmu. Vairāk pareizi, augšējā un apakšējā robeža uz runtime. Labākajā gadījumā par bināro meklēšanu, mūsu elements ir turpat vidū, un jūs saņemsiet to pastāvīgu laiku, Nav svarīgi, cik liels ir masīva pārējais ir. Simbols, ko izmanto tas ir Ω. Tātad, šis algoritms ir teikt palaist Ω (1). Labākajā gadījumā, tas atrod elements ātri, Nav svarīgi, cik liels masīvs ir, bet sliktākajā gadījumā, tai jāpilda (log n) split pārbaudes masīva lai atrastu pareizo elementu. Sliktākajā gadījumā augšējās robežas ir minēti ar lielo "O" ka jūs jau zināt. Tātad, tas ir O (log n), bet Ω (1). 

Lineāra meklēt, gluži pretēji, kurā jums staigāt pa katru elementu masīva lai atrastu vienu vēlaties, labākajā Ω (1). Atkal, pirmais elements jūs vēlaties. Tātad, tas nav svarīgi, cik liels masīvs ir. Sliktākajā gadījumā, tas ir pēdējais elements masīva. Tātad, jums ir staigāt pa visiem n elementu masīvu, lai atrastu to, piemēram, ja jūs meklējat 3. Tātad, tas darbojas O (n) laikā jo tas ir proporcionāls skaits elementu masīvā. 

Vēl viens lietots simbols ir Θ. To var izmantot, lai aprakstītu algoritmu, kur vislabāk un sliktākajā gadījumā ir vienādi. Tas ir gadījums, kas virknes garuma algoritmu mēs runājām par agrāk. Tas ir, ja mēs to uzglabā mainīgā pirms mēs saglabājam stīgu un tai piekļūt vēlāk pastāvīgu laiku. Nav svarīgi, ko skaits mēs esam uzglabājot šajā mainīgo, mums būs jāskatās uz to. Labākais lieta ir, mēs skatāmies uz to un atrast garumu virknes. Tātad Ω (1) vai labākajā gadījumā nemainīgs laika. Sliktākajā gadījumā ir, mēs skatāmies uz to un atrast garumu virknes. Tātad, O (1) vai pastāvīgs laiks sliktākajā gadījumā. Tātad, jo labākajā gadījumā un sliktākajā gadījumā, ir tas pats, to var teikt darboties Θ (1) laikā. 

Rezumējot, mums ir labas iespējas, lai tādēļ par kodiem efektivitāti nezinot neko par reālās pasaules laika tās veic, lai palaistu, kas ietekmē daudz ārējo faktoru, tostarp atšķiras aparatūras, programmatūras, vai specifiku jūsu kodu. Arī tas ļauj mums pamatojusi arī par to, kas notiks ja lielumu ievadē palielinās. 

Ja jūs darbojas O (n) ² algoritmu, vai vēl ļaunāk, O (2 ⁿ) algoritms, viena no visstraujāk augošajām veidi, jūs tiešām sāk pamanīt palēninājumu kad jūs sākat strādāt ar lielāku datu apjomu. 

Tas ir asimptotiskā sarežģītību. Paldies.