Bone, do, komputa komplikeco. Nur iom de averto antaŭ ni plonĝi en tro far-- tiu verŝajne estos inter la plej math-multepezaj ni raportas en CS50. Espereble ne estos tro superforta kaj ni provos gvidi vin tra la procezo, sed nur iom de justa averto. Ekzistas iomete de matematiko implikita tie. Bone, do por fari uzo de nia komputa rimedoj en la reala world-- estas vere Gravas kompreni algoritmoj kaj kiel ili procesi datumojn. Se ni havas vere kompetenta algoritmo, ni povas minimumigi la kvanton de resursoj ni havas disponebla por trakti ĝin. Se ni havas algoritmon kiu tuj prenos multan laboron procesi vere granda aro de datumoj, ĝi estas tuj postulos pli kaj pli da rimedoj, kiuj estas mono, RAM, ĉiuj tian materialon. 

Do, povante analizi algoritmo uzanta tiun ilon aro, esence, demandas la question-- kiel faras ĉi tiu algoritmo skalo kiel ni ĵeti pli kaj pli datumoj en ĝi? En CS50, la kvanto de datumoj ni estas laborante kun estas belaj malgrandaj. Ĝenerale, niaj programoj estas irantaj kuri en dua aŭ less-- probable multe malpli aparte frue sur. 

Sed pensu pri kompanio kiu traktas kun centoj da milionoj de klientoj. Ili devas prilabori ke klienta datumo. Kiel la nombro de klientoj ili havi ricevas pli kaj pli grandaj, ĝi tuj postulas pli kaj pli rimedoj. Kiel multaj pli rimedoj? Nu, tio dependas de kiel ni analizos la algoritmo, uzante la ilojn en tiu toolbox. Kiam ni parolas pri la komplekseco de an algorithm-- kiuj foje vi instruos vin aŭskultos referita kiel tempo komplekseco aŭ spaca komplikeco sed ni ĵus tuj voki complexity-- ni ĝenerale parolas pri la plej malbona-kazo scenaro. Donita la absoluta plej malbona stako de datumoj kiuj ni povus ĵeti ĝin, kiele tiu algoritmo tuj procesi aŭ trakti ke datumoj? Ni ĝenerale nomas la plej malbona-kazo ekzekuto de algoritmo granda-O. Do algoritmo povus esti dirita kuri en O de n aŭ O de n kvadratoj. Kaj pli pri kio tiuj signifas en sekundo. 

Kelkfoje, tamen, ni faru prizorgo pri la plej kazo scenaro. Se la datumoj estas ĉio ni volis ĝin esti kaj estis absolute perfekta Kaj ni estis sendanta tiun perfekta aro de datumoj per nia algoritmo. Kial ne pritrakti en tiu situacio? Ni foje rilati al tio kiel big-Omega, do en kontrasto kun granda-O, ni havas granda-Omega. Big-Omega por la plej kazo scenaro. Big-O por la plej malbona-kazo scenaro. Ĝenerale, kiam oni parolas pri la komplikeco de algoritmo, ni parolas pri la plej malbona-kazo scenaro. Observu do, ke en menso. 

Kaj en ĉi tiu klaso, ni ĝenerale irante forlasi la strikta analizo flanken. Ekzistas sciencoj kaj kampoj dediĉita al tiu klaso de aĵoj. Kiam ni parolas pri rezonado tra algoritmoj, kion ni faros pecon-post-peco por multaj algoritmoj ni raportas en la klaso. Ni vere nur parolas pri diskutis tra ĝi kun komuna senso, Ne kun formuloj, aŭ pruvoj, aŭ io simila. Do ne zorgu, ni ne estos igante granda math klaso. 

Do mi diris, ke ni zorgas pri komplekseco ĉar ĝi petas la demandon, kiamaniere ĉu nia algoritmoj manipuli pli grandajn kaj grandaj datenaroj estanta ĵetita ĉe ili. Nu, kio estas datumoj aro? Kion mi volas diri kiam mi diras ke? Ĝi signifas ajn faras la plej senco en kunteksto, por esti honesta. Se ni havas algoritmon, la Procezoj Strings-- ni probable parolante pri la grandeco de la kordo. Jen la datumoj set-- la grandeco, la nombro de karakteroj kiuj konsistigas la kordo. Se ni parolas pri algoritmo kiu procesas dosierojn, Ni povus esti parolante pri kiom multaj kilobajtoj konsistas ke dosiero. Kaj tio estas la datuma aro. Se ni parolas pri algoritmo kiu manipulas arrays pli ĝenerale, kiel ordigado algoritmoj aŭ serĉanta algoritmoj, ni probable parolas pri la nombro de elementoj kiuj formas parton tabelo. 

Nun, ni povas mezuri la algorithm-- precipe, kiam mi diras ni povas mezuri algoritmo, mi signifas ni povas mezuri kiom multaj rimedoj prenas supren. Cxu tiuj rimedoj estas, kiom da bajtoj de RAM-- aŭ megabajtoj de RAM ĝi uzas. Aŭ kiom tempo prenas kuri. Kaj ni povas nomi ĉi mezuri, arbitre, f de n. Kie n estas la nombro de elementoj en la datuma aro. Kaj f de n estas kiom multaj somethings. Kiom da unuoj de rimedoj faras ĝi postulas procesi ke datumoj. 

Nun, ni efektive ne gravas pri kio f de n estas ĝuste. Fakte, ni tre malofte will-- certe neniam en ĉi class-- mi plonĝi en ajnan vere profunda analizo de kion f de n estas. Ni nur tuj paroli pri kion f de n estas proksimume kia ĝi emas. Kaj la tendenco de algoritmo estas diktita de ĝia plej alta ordo terminon. Kaj ni povas vidi kion mi signifas ke prenante Rigardu pli konkretan ekzemplon. 

Do diru ke ni havas tri malsamaj algoritmoj. La unua el kiuj prenas n Cubed, iuj unuecoj de rimedoj procesi datuma aro de amplekso n. Ni havas dua algoritmo kiu prenas n Cubed plus n kvadratoj rimedoj procesi datuma aro de amplekso n. Kaj ni havas trian algoritmo kiu kuras in-- ke dissxutas n Cubed minus 8n kvadrato plus 20 n unuoj de rimedoj procesi algoritmo kun datuma aro de amplekso n. 

Nun denove, ni vere ne tuj enir tiu nivelo de detalo. Fakte, mi nur havas tiujn supren tie kiel ilustraĵo de punkto ke mi tuj estos farante en sekundo, kio estas ke ni nur vere zorgas pri la tendenco de aferoj kiel la datenaroj pligrandiĝi. Do se la datuma aro estas malgrandaj, ekzistas fakte iom granda diferenco en tiuj algoritmoj. La tria algoritmo tie prenas 13 fojojn pli longaj, 13 fojojn la kvanto de rimedoj kuri relativa al la unua unu. 

Se niaj datumoj aro estas grandeco 10, kiu estas pli granda, sed ne nepre grandega, ni povas vidi ke ekzistas efektive iom de diferenco. La tria algoritmo iĝas pli efika. Temas pri vere 40% - aŭ 60% pli eficientes. Ĝi prenas 40% la kvanto de tempo. Ĝi povas run-- povas preni 400 ekzemplerojn de rimedoj prilabori datumojn pri grandeco 10. Dum la unua algoritmo, kontraste, prenas 1.000 rimedoj prilabori datumojn pri grandeco 10. Sed vidu kio okazas kiam niaj nombroj akiri eĉ pli granda. 

Nun, la diferenco inter tiuj algoritmoj komencas fariĝi iom malpli evidenta. Kaj la fakto ke ekzistas malsupra ordo terms-- aŭ prefere, terminoj kun suba exponents-- komenci fariĝi pala. Se datuma aro estas de grandeco 1.000 kaj la unua algoritmo kuras en miliardo paŝoj. Kaj la dua algoritmo kuras en miliardo kaj miliono paŝoj. Kaj la tria algoritmo kuras en ĵus timema de miliardo paŝoj. Estas preskaux miliardo paŝoj. Tiuj malsupra ordo esprimoj komenci fariĝi vere pala. Kaj ĝuste por vere martelo domo la point-- se la datumoj enigo estas de grandeco a million-- ĉiuj tri de ĉi tiuj preskaux preni unu quintillion-- se mia math estas correct-- paŝoj prilabori datumojn enigo de grandeco miliono. Tio estas multe da ŝtupoj. Kaj la fakto ke unu el ili povus preni paron 100.000, aŭ paro 100 milionoj eĉ malpli kiam ni parolas pri kelkaj ke big-- estas afable pala. Ili ĉiuj emas preni proksimume n Cubed, kaj tiaj ni estus reale rilati al ĉiuj tiuj algoritmoj kiel estante sur la ordo de n Cubed aŭ granda-O de n potenco de. 

Jen listo de iuj el la pli komuna komputa komplikeco klasoj ke ni renkontas en algoritmoj, ĝenerale. Kaj ankaŭ specife en CS50. Tiuj estas ordonitaj de ĝenerale plej rapida ĉe la supro, al ĝenerale malrapida ĉe la fundo. Do konstanta tempo algoritmoj tendencas esti la plej rapida, sendepende de la grandeco de la datumoj enigo sekvinberoj en. Ili ĉiam preni unu operacion aŭ unu unuo de rimedoj por trakti. Ĝi povus esti 2, oni eble esti 3, eble 4. Sed estas konstanta nombro. Ĝi ne varias. 

Logaritma tempo algoritmoj estas iomete pli bone. Kaj vere bona ekzemplo de logaritma tempo algoritmo Vi certe vidis nun estas la ŝirante dise de la telefono libro trovi Mike Smith en telefono libro. Ni tranĉas la problemo en duono. Kaj tiel kiel n prenas pli granda kaj pli granda kaj larger-- fakte, ĉiufoje vi duobligi n, ĝi nur prenas pli paŝo. Do jen multa bona ol, ni diru, lineara tempo. Kio estas se vi duobligos n, ĝi prenas duobla la nombro de paŝoj. Se vi triobligi n, prenas triobligi la nombron de paŝoj. Unu paŝo por unueco. 

Tiam aĵoj iom more-- iom malpli granda de tie. Vi havas lineara ritmaj tempo, kelkfoje nomata log lineara tempo aŭ simple n log n. Kaj ni vidos ekzemplon de algoritmo ke kurojn en n log n, kio estas ankoraŭ pli bona ol kvadrata time-- n kvadratoj. Aŭ polinoma tempo, n du ajna nombro pli granda ol du. Aŭ eksponenta tempo, kio estas eĉ worse-- C al la n. Do iu konstanto nombro altigita al la potenco de la grandeco de la enigaĵo. Do, se estas 1,000-- se la datumoj enigo estas de grandeco 1.000, necesus C al la 1,000 potenco. Estas multe pli malbone ol polinoma tempo. 

Faktorialo tempo estas eĉ pli malbona. Kaj fakte, tie vere fari ekzistas senfina tempo algoritmoj, kiel, tiel nomata stulta sort-- kies laborposteno estas hazarde barajar tabelo kaj tiam kontrolu vidi ĉu ĝi estas ordo. Kaj se ĝi ne estas, hazarde barajar la tabelo denove kaj kontrolu ĉu ĝi estas ordo. Kaj kiel vi povas verŝajne imagine-- vi povas imagi situacion kie en la plej malbona kazo, ke volo neniam efektive komenci kun la tabelo. Ke algoritmo estus kuri eterne. Kaj tial estus malfinia tempa algoritmo. Espereble vi ne skribos ajna faktorialo aŭ senfina tempo algoritmoj en CS50. 

Do, ni prenu iom pli konkreta rigardi kelkaj simplaj komputa komplekseca klaso. Do ni havas example-- aŭ du ekzemplojn here-- de konstanta tempo algoritmoj, kiu ĉiam preni sola operacio en la plej malbona kazo. Do la unua example-- ni havas funkcion nomita 4 por vi, kiuj prenas tabelo de amplekso 1.000. Sed tiam ŝajne fakte ne aspektas ĉe it-- ne vere zorgas kio estas interne de ĝi, de tiu tabelo. Ĉiam ĵus revenas kvar. Do, tiu algoritmo, spite la fakton ke ĝi prenas 1.000 elementoj ne fari nenion kun ili. Nur revenas kvar. Ĝi ĉiam estas sola paŝo. 

Fakte, aldonu 2 nums-- kiu ni vidis antaŭe kiel well-- nur procesas du entjeroj. Ĝi ne estas sola paŝo. Ĝi estas fakte paro paŝoj. Vi ricevas, vi ricevas b, vi aldonas ilin kune, kaj ci elirigos la rezultoj. Do estas 84 paŝoj. Sed estas ĉiam konstanto, nekonsiderante a aŭ b. Vi devas akiri, atingi b, aldonu ili kune, eligo la rezulto. Do tio estas konstanta tempo algoritmo. 

Jen ekzemplo de lineara tempo algorithm-- algoritmo kiu gets-- kiu prenas unu plian paŝon, eble, kiel via enigo kreskas per 1. Do, diru ni serĉas la nombro 5 ene de tabelo. Vi povus havi situacion kie vi povas trovi ĝin sufiĉe frue. Sed vi povus ankaŭ havi situacio kie eble estos la lasta elemento de la tabelo. En tabelo de amplekso 5, se ni serĉas la numero 5. Ĝi prenus 5 paŝoj. Kaj fakte, imagu ke ekzistas Ne 5 ie en tiu tabelo. Ni ankoraŭ vere devas rigardi ĉiu unuopa elemento de la tabelo por determini ĉu 5 estas tie. 

Do en la plej malbona kazo, kio estas ke la elemento estas lasta en la tabelo aŭ ne ekzistas entute. Ni ankoraŭ devas rigardi ĉiuj de la n elementoj. Kaj tial tiu algoritmo kuras en lineara tempo. Vi povas konfirmi ke extrapolar iomete dirante, se ni havis 6-era tabelo kaj ni serĉis la numero 5, ĝi povus preni 6 paŝoj. Se ni havas 7-era tabelo kaj ni serĉas la numero 5. Ĝi povus preni 7 paŝoj. Kiel ni aldonos unu pli elementon al nia tabelo, ĝi prenas pli paŝo. Tio lineara algoritmo en la plej malbona kazo. 

Paro rapide demandoj por vi. Kio estas la runtime-- kio estas la plej malbona-kazo tempo de ekzekuto de tiu aparta fragmento de kodo? Do mi havas 4 buklo tie ke kuroj el j egalas 0, tuta vojo supren al m. Kaj kion mi vidas ĉi tie, estas ke la korpo de la banto kuras en konstanta tempo. Do uzante la terminologion ke ni jam parolis about-- kio estus la plej malbona-kazo ekzekuto de ĉi tiu algoritmo? Prenu duan. La ena parto de la buklo kuras en konstanta tempo. Kaj la ekstera parto de la buklo tuj kuri m fojojn. Do kio estas la plej malbona-kazo tempo de ekzekuto tie? Ĉu vi divenas grand-O de m? Vi estus prava. 

Kion pri alia? Ĉi tiu fojo ni havas buklo ene de banto. Ni havas eksteran banton kiu kuras de nulo al p. Kaj ni havas internan banton kiu kuras de nulo al p, kaj ene de tiu, Mi deklaras ke la korpo la buklo kuras en konstanta tempo. Do kio estas la plej malbona-kazo tempo de ekzekuto de tiu aparta fragmento de kodo? Nu, denove, ni havas ekstera buklo kiu kuras p fojojn. Kaj ĉiu time-- ripeto de tiu buklo, prefere. Ni havas internan banton kiu ankaŭ kuras p fojojn. Kaj tiam ene de tiu, estas la konstanta time-- iom fragmento tie. 

Do se ni havas eksteran banton ke kuras p fojojn ene de kiuj estas ena buklo ke kuras p times-- kio estas la plej malbona-kazo tempo de ekzekuto de tiu fragmento de kodo? Ĉu vi divenas grand-O de p kvadrato? 

Mi Doug Lloyd. Jen CS50.