Tout dwa, se konsa, enfòmatik konpleksite. Jis yon ti jan nan yon avètisman anvan nou plonje nan twò far-- sa a ap pwobableman dwe nan mitan bagay ki pi matematik-lou nou pale sou nan CS50. Nou swete ke li pa pral twò akablan epi n ap eseye ak gide ou atravè tout pwosesis la, men jis yon ti jan nan yon avètisman ki jis. Genyen yon ti jan nan matematik ki enplike isit la. Tout dwa, se konsa nan lòd fè pou sèvi ak resous enfòmatik nou an nan world-- nan byen li vrèman enpòtan ke ou konprann algoritm ak ki jan yo travay sou done. Si nou gen yon reyèlman algorithm efikas, nou kapab minimize kantite lajan an nan resous nou genyen disponib fè fas ak li. Si nou gen yon algorithm ki se pral pran yon anpil nan travay nan pwosesis yon vrèman gwo ansanm done, li la ale nan mande pou plis ak plis resous, ki se lajan, RAM, tout sa ki kalite bagay. 

Se konsa, ke yo te kapab analize yon algorithm lè l sèvi avèk sa a seri zouti, fondamantalman, mande question-- nan ki jan fè sa a algorithm echèl jan nou voye jete pi plis ak plis done nan li? Nan CS50, kantite lajan an nan done nou ap travay ak se trè piti. Anjeneral, pwogram nou yo ale nan kouri nan yon dezyèm oswa yon less-- pwobableman yon anpil mwens patikilyèman byen bonè nan. 

Men, panse osijè de yon konpayi ki kontra ak dè santèn de dè milyon de kliyan yo. Apre sa, yo bezwen nan pwosesis ke kliyan done. Kòm kantite kliyan yo gen vin pi gwo ak pi gwo, li k ap pase yo mande pou pi plis ak plis resous. Konbyen plis resous? Oke, ki depann sou ki jan nou analize algorithm a, lè l sèvi avèk zouti yo nan bwat zouti sa a. Lè nou pale sou konpleksite a nan yon algorithm ki pafwa ou pral tande l 'refere yo kòm tan konpleksite oswa espas konpleksite men nou ap jis ale yo rele complexity-- nou ap jeneralman pale de pi move-ka senaryo a. Bay absoli pil la pi mal la nan done ke nou te kapab voye nan li, ki jan se sa a algorithm pral travay oswa fè fas ak ke done? Nou jeneralman rele pi move-ka a ègzekutabl nan yon algorithm gwo-O. Se konsa, ta ka yon algorithm dwe di kouri nan O nan n oswa O nan n okib. Ak plis ankò sou sa moun vle di nan yon dezyèm fwa. 

Pafwa, menm si, nou fè swen sou senaryo a pi byen ki ka. Si done a se tout sa nou te vle li nan dwe epi li te absoliman pafè epi nou te voye sa a pafè mete nan done nan algorithm nou an. Ki jan li ta okipe nan ki sitiyasyon? Nou pafwa, al gade nan ke kòm gwo-Omega, se konsa nan kontra ak gwo-O, nou gen gwo-Omega. Big-Omega pou senaryo a pi byen ki ka. Big-O pou senaryo ki pi mal la-ka. Anjeneral, lè nou pale sou konpleksite nan yon algorithm, n ap pale a pi move-ka senaryo. Se konsa, kenbe sa nan tèt ou. 

Ak nan klas sa a, nou ap jeneralman ale yo kite analiz la solid sou kote. Gen syans ak lòt jaden konsakre nan sa a kalite bagay. Lè nou pale sou rezònman a algoritm, ki nou pral fè moso-pa-moso pou anpil algoritm nou pale sou nan klas la. Nou ap vrèman jis ap pale de rezònman nan li ak sans komen, pa avèk fòmil, oswa prèv, oswa yon bagay tankou sa. Se konsa, pa enkyete w, Nou pa pral vire nan yon klas matematik gwo. 

Se konsa, mwen te di nou pran swen sou konpleksite paske li mande kesyon an, ki jan algoritm nou an okipe pi gwo ak pi gwo kouche done ke yo te voye jete nan yo. Oke, sa se yon seri done? Ki sa mwen vle di lè m 'te di ke? Sa vle di tou sa fè pi plis nan sans nan yon kontèks, yo dwe onèt. Si nou gen yon algorithm a, Pwosesis strings nou ap pwobableman ap pale de gwosè a nan fisèl la. Sa a done yo set-- gwosè a, nimewo a nan karaktè ki fè moute fisèl la. Si nou ap pale sou yon algorithm ki trete dosye, nou ta ka dwe pale sou ki jan anpil kilookte genyen ki dosye-a. Epi sa a, mete nan done. Si nou ap pale de yon algorithm ki okipe zafè ranje plis jeneralman, tankou klasman algoritm oswa chèche algoritm, nou ap pwobableman ap pale de nimewo a nan eleman ki genyen yon etalaj. 

Koulye a, nou ka mezire yon algorithm an patikilye, lè m 'di sa nou kapab mezire yon algorithm, mwen vle di nou ka mezire ki anpil resous li pran yo. Si resous sa yo se, ki jan anpil bytes nan RAM-- oswa megabit nan RAM li itilize. Ou konbyen tan li pran yo kouri. Apre sa, nou ka rele sa a mezire, abitrèman, f nan n. Ki kote n se nimewo a nan eleman nan ansanm done a. Apre sa, f nan n se ki jan anpil nouvote. Konbyen inite nan resous fè li mande pou nan pwosesis ki done. 

Koulye a, nou aktyèlman pa pran swen sou sa ki f nan n se egzakteman. An reyalite, nou trè raman will-- sètènman pral pa janm nan sa a mwen class-- plonje nan gwo twou san fon vrèman nenpòt analiz de sa f nan n se. Nou ap jis ale nan pale sou sa f nan n se apeprè oswa ki sa li gen tandans fè. Apre sa, tandans a nan yon algorithm se dikte nan tèm pi wo lòd li yo. Apre sa, nou ka wè ki sa mwen vle di pa ki lè yo pran yon gade nan yon egzanp plis konkrè. 

Se konsa nou di ke nou gen twa algoritm diferan. Premye a nan ki te pran n Gleason, gen kèk inite nan resous nan pwosesis yon seri done nan gwosè n. Nou gen yon algorithm dezyèm ki pran n Gleason plis n okib resous nan pwosesis yon seri done nan gwosè n. Epi nou gen yon twazyèm algorithm ki kouri in-- ki pran moute n Gleason mwens 8n okib plis 20 N inite nan resous nan pwosesis yon algorithm ak done mete nan gwosè n. 

Koulye a, ankò, nou reyèlman pa pral jwenn nan nivo sa a nan detay. Mwen vrèman jis gen sa yo moute isit la tankou yon demonstrasyon pou montre yon pwen ke mwen pral yo dwe fè nan yon dezyèm lan, ki se ke nou sèlman reyèlman sousye sou tandans nan de bagay sa yo kòm ansanm sa yo, done jwenn pi gran. Se konsa, si ansanm done a se piti, gen nan aktyèlman yon bèl gwo diferans nan algoritm sa yo. Algorithm nan twazyèm gen pran 13 fwa pi long, 13 fwa kantite lajan an nan resous nan kouri relatif nan yon sèl la an premye. 

Si nou an seri done se gwosè 10, ki se pi gwo, men se pa nesesèman gwo, nou ka wè ke gen nan aktyèlman yon ti jan nan yon diferans. Algorithm nan twazyèm vin pi efikas. Li nan sou aktyèlman 40% - oswa 60% pi efikas. Li pran 40% kantite lajan an nan tan. Li ka run-- li ka pran 400 inite nan resous nan pwosesis yon seri done nan gwosè 10. Lè nou konsidere ke premye a algorithm, pa kontra, pran 1,000 inite nan resous nan pwosesis yon seri done nan gwosè 10. Men, gade sa k ap pase kòm nimewo nou an jwenn menm pi gran. 

Koulye a, diferans ki genyen ant sa yo algoritm kòmanse vin yon ti kras mwens aparan. Ak lefèt ke gen pi ba-lòd terms-- ou pito, tèm ak pi ba exponents-- kòmanse vin petinan. Si yon seri done se nan gwosè 1,000 ak algorithm nan premye kouri nan yon milya dola etap. Men dezyèm algorithm nan kouri nan yon milya dola ak yon milyon dola etap. Ak twazyèm algorithm nan kouri nan jis timid nan yon milya dola etap. Li nan bèl anpil yon milya dola etap. Moun sa yo ki tèm pi ba-lòd kòmanse yo vin reyèlman petinan. Epi jis reyèlman mato lakay point-- nan si D 'a done se nan gwosè yon million-- tout twa nan sa yo bèl anpil pran yonn quintillion-- si matematik mwen an se etap correct-- nan pwosesis yon D 'done nan gwosè yon milyon dola. Sa se yon anpil nan etap. Ak lefèt ke youn nan yo ta ka pran yon koup 100,000, oswa yon koup 100 milyon dola menm mwens lè nou ap pale de yon PO ki big-- li nan kalite petinan. Yo tout gen tandans pran apeprè n Gleason, epi pou nou ta aktyèlman al gade nan tout nan algoritm sa yo tankou se te sou lòd la nan n Gleason oswa gwo-O nan n Gleason. 

Isit la nan yon lis kèk nan plis nan klas komen konpleksite enfòmatik ke nou pral rankontre nan algoritm, jeneralman. Epi tou espesyalman nan CS50. Sa yo te bay lòd soti nan jeneralman pi rapid nan tèt la, jeneralman plus nan fon. Se konsa, algoritm tan konstan gen tandans yo dwe pi rapid la, kèlkeswa nan gwosè a nan la D 'done ou pase nan. Yo toujou pran yonn operasyon oswa yon inite nan resous fè fas ak. Li ta ka 2, li ta ka dwe 3, li ta kapab 4. Men, li la yon PO konstan. Li pa varye. 

Algoritm tan logaritmik se yon ti kras pi byen. Ak yon reyèlman bon ekzanp de yon algorithm tan logaritmik ou te siman wè pa kounye a se nan chire apa nan liv la telefòn jwenn Mike Smith nan liv la telefòn. Nou koupe pwoblèm nan nan mwatye. Se konsa, kòm n vin pi gwo ak pi gwo ak larger-- an reyalite, chak fwa ou double n, li sèlman pran yon sèl etap plis. Se konsa, sa a, se yon anpil pi bon pase, di, tan lineyè. Ki se si ou double n, li pran doub kantite etap. Si ou trip n, li pran trip ki kantite etap. Yon sèl etap pou chak inite. 

Lè sa a, bagay sa yo jwenn yon ti kras more-- ti kras mwens gwo soti nan la. Ou gen lineyè tan rit, pafwa rele boutèy demi lit tan lineyè oswa jis n boutèy demi lit n. Epitou, n ap yon egzanp nan yon algorithm ki kouri nan n boutèy demi lit n, ki se toujou pi bon pase kwadratik time-- n okib. Oswa tan polinòm, n de nenpòt ki kantite pi gran pase de. Oswa tan eksponansyèl, ki se menm worse-- C rive nan n nan. Se konsa, kèk nimewo konstan leve soti vivan nan pouvwa a nan gwosè a nan D 'a. Se konsa, si gen nan 1,000-- si nan D 'done se nan gwosè 1,000, li ta pran C rive nan pouvwa a 1,000 th. Li se yon anpil pi mal pase tan polinòm. 

Faktoryèl tan se menm vin pi mal. Ak nan reyalite, gen reyèlman fè egziste algoritm tan enfini, tankou, sa yo rele estipid sort-- ki gen travay se yo chefeul owaza yon etalaj ak Lè sa a tcheke yo wè si wi ou non li nan Ranje. Men, si li pa, owaza chefeul etalaj la ankò epi tcheke yo wè si wi ou non li nan Ranje. Ak jan ou ka pwobableman imagine-- ou ka imajine yon sitiyasyon kote nan pi move-ka a, ki volonte pa janm aktyèlman kòmanse ak etalaj la. Sa algorithm ta kouri pou tout tan. Se konsa, ki ta ka yon enfini tan algorithm. Nou swete ke ou pa pral ekri nenpòt ki lè faktoryèl oswa enfini algoritm nan CS50. 

Se konsa, kite a pran yon ti kras pi plis gade konkrè nan kèk ki pi senp enfòmatik konpleksite klas yo. Se konsa, nou gen yon example-- oswa de egzanp isit lan-- a algoritm tan konstan, ki toujou pran yon operasyon yon sèl nan pi move-ka-a. Se konsa, nan premye example-- nou gen yon fonksyon rele 4 pou ou, ki pran yon etalaj de gwosè 1,000. Men, Lè sa aparamman pa aktyèlman gade a l-- pa reyèlman sousye sa ki nan andedan nan li, nan ki etalaj. Toujou jis retounen kat. Se konsa, ki algorithm, malgre lefèt ke li pran 1,000 eleman pa fè anyen ak yo. Jis retounen kat. Li nan toujou yon etap sèl. 

An reyalite, ajoute 2 nums-- ki nou te wè anvan kòm well-- jis trete de nonm antye relatif. Li pa yon etap sèl. Li nan aktyèlman etap yon koup. Ou jwenn yon, ou jwenn b, ou ajoute yo ansanm, epi ou pwodiksyon rezilta yo. Se konsa, li 84 etap. Men, li la toujou konstan, kèlkeswa yon oswa b. Ou gen yo ka resevwa yon, jwenn b, ajoute yo ansanm, pwodiksyon rezilta a. Se konsa, sa a, se yon algorithm tan konstan. 

Isit la nan yon egzanp sou yon lineyè algorithm tan yon algorithm ki gen- ki pran yon sèl etap adisyonèl, petèt, kòm opinyon ou a ap grandi pa 1. Se konsa, kite pou nou di nou ap chèche pou nimewo 5 anndan an nan yon etalaj. Ou ta ka gen yon sitiyasyon kote ou ka jwenn li san patipri byen bonè. Men, ou te kapab gen tou yon sitiyasyon kote li ta ka eleman nan sot pase yo nan etalaj la. Nan yon etalaj de gwosè 5, si nou ap chèche pou yon nimewo pou la 5. Li ta pran 5 etap. Lè an reyalite, imajine ke gen nan pa nenpòt kote nan 5 etalaj sa a. Nou toujou gen aktyèlman fè yon gade nan chak eleman sèl nan etalaj la nan lòd yo detèmine si wi ou non 5 ki gen la. 

Se konsa, nan pi move ka a-yo, ki se ke eleman nan se dènye nan etalaj la oswa pa egziste nan tout. Nou toujou gen fè yon gade nan tout nan eleman yo n. Se konsa, sa a algorithm kouri nan tan lineyè. Ou ka konfime ke pa èkstrapolan yon ti jan lè li di, si nou te gen yon etalaj 6-eleman ak nou te kap chèche nimewo a 5, li ta ka pran 6 etap. Si nou gen yon etalaj 7-eleman ak nou ap chèche pou yon nimewo pou la 5. Li ta ka pran 7 etap. Kòm nou ajoute yon sèl eleman plis nan nou an etalaj, li pran yon sèl etap plis. Sa se yon algorithm lineyè nan pi move-ka-a. 

Koup kesyon rapid pou ou. Ki sa ki nan runtime-- nan sa ki nan pi move ka-ègzekutabl nan nan sa a brib patikilye nan Kòd? Se konsa, mwen gen yon riban 4 isit la ki kouri soti nan j egal 0, tout wout la jiska m. Apre sa, sa m ap wè isit la, se ke nan kò a riban an kouri nan tan konstan. Se konsa, lè l sèvi avèk tèminoloji a ki nou te deja pale sou- sa ta dwe pi mal la-ka a ègzekutabl nan algorithm sa a? Pran yon dezyèm fwa. Pati nan anndan an nan bouk la kouri nan tan konstan. Ak yon pati la deyò nan la bouk ki pral kouri m fwa. Se konsa, sa ki nan ègzekutabl ki pi mal la-ka isit la? Èske w te devine gwo-O nan m? Ou ta dwe gen dwa. 

Kouman sou yon lòt yon sèl? Fwa sa a, nou gen yon bouk andedan nan yon riban. Nou gen yon riban deyò ki kouri soti nan zewo rive p. Epi nou gen yon riban ki kouri anndan soti nan zewo rive p, ak andedan nan sa, Mwen deklare ke nan kò a bouk kouri nan tan konstan. Se konsa, sa ki nan ègzekutabl ki pi mal la-ka nan sa a brib patikilye nan Kòd? Bon, ankò, nou gen yon deyò bouk ki kouri fwa p. Epitou, chak iterasyon time-- nan ki bouk, olye. Nou gen yon riban enteryè ki tou kouri fwa p. Lè sa a, andedan nan ki, gen nan la konstan time-- ti kras brib a. 

Se konsa, si nou gen yon riban deyò ki kouri fwa p andedan nan ki se yon bouk enteryè ki kouri p jou- ki sa ki pi move ka-ègzekutabl nan nan sa a brib nan kòd? Èske w te devine gwo-O nan p au? 

Mwen se Doug Lloyd. Sa a se CS50.