[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.