Lahat ng karapatan, kaya, computational kumplikado. Lamang ng isang piraso ng isang babala bago namin sumisid sa masyadong far-- Makikita ito ay marahil ay kabilang sa ang mga bagay na pinaka-math-mabigat usapan namin tungkol sa CS50. Sana ito ay hindi masyadong napakalaki at susubukan naming at gagabay sa iyo sa pamamagitan ng proseso, ngunit lamang ng isang piraso ng isang makatarungang babala. May isang maliit na piraso ng math kasangkot dito. Lahat ng karapatan, kaya upang gumawa ng paggamit ng aming computational mapagkukunan sa tunay na world-- ito ay talagang Mahalaga na maunawaan na algorithm at kung paano sila proseso data. Kung kami ay may isang tunay na mahusay na algorithm, kami ay maaaring mabawasan ang dami ng mga mapagkukunan mayroon kaming magagamit sa pakikitungo sa mga ito. Kung kami ay may isang algorithm na ay pagpunta sa tumagal ng maraming trabaho upang i-proseso ang isang tunay na malaking hanay ng data, ito ay pagpunta sa nangangailangan ng mas maraming at mas maraming mga mapagkukunan, na kung saan ay pera, RAM, lahat na uri ng mga bagay-bagay. 

Kaya, na makaka-aralan ang isang algorithm gamit ang tool na set, talaga, itatanong ng question-- kung paano gumagana ang scale algorithm bilang ihagis namin ang higit pa at mas maraming data at ito? Sa CS50, ang halaga ng data hindi namin nagtatrabaho sa ay medyo maliit. Sa pangkalahatan, ang aming mga programa ay pagpunta upang tumakbo sa isang segundo o less-- marahil ng isang pulutong ng mas kaunting lalo na sa maagang bahagi. 

Ngunit isipin ang tungkol sa isang kumpanya na trato sa daan-daang milyon-milyong mga customer. At kailangan nila upang i-proseso na data ng customer. Bilang ng bilang ng mga customer nila Mayroon makakakuha ng mas malaki at mas malaki, ito ay nangangailangan ng pagpunta sa mas at mas maraming mga mapagkukunan. Paano marami pang resources? Well, na depende sa kung gaano kami ay suriin ang algorithm, gamit ang mga tool na ito sa toolbox. Kapag pinag-uusapan natin ang pagiging kumplikado ng isang algorithm-- na kung minsan ay makikita mo marinig ito tinutukoy bilang oras kumplikado o space kumplikado ngunit lamang namin ang pagpunta upang tumawag complexity-- pangkalahatan ay pinag-uusapan natin ang tungkol sa ang pinakamasama-case na sitwasyon. Dahil sa ang ganap na pinakamasama tumpok ng data na maaaring namin ay ibinabato sa ito, kung paano ang algorithm na ito ng pagpunta sa iproseso o pakikitungo sa mga na data? Karaniwan naming tawagan ang pinakamasama-case runtime ng isang algorithm big-O. Kaya ay maaaring sinabi ng isang algorithm upang tumakbo sa O ng n o O ng n squared. At higit pa tungkol sa kung ano mga ibig sabihin sa isang segundo. 

Minsan, bagaman, ang ginagawa namin pag-aalaga tungkol sa mga pinakamahusay na-case na sitwasyon. Kung ang data ay ang lahat ng bagay na gusto naming ito upang maging at ito ay ganap na perpekto at kami ay pagpapadala ito perpekto set ng data sa pamamagitan ng aming algorithm. Paano ito ay hawakan sa na sitwasyon? Minsan naming sumangguni sa na bilang big-Omega, para sa mga kaibahan sa mga malaking-O, kami ay may malaking-Omega. Big-Omega para sa pinakamahusay na-case na sitwasyon. Big-O para sa pinakamasama-case na sitwasyon. Karaniwan, kapag ang pinag-uusapan natin ang pagiging kumplikado ng isang algorithm, pinag-uusapan natin ang tungkol sa mga pinakamasama-case na sitwasyon. Kaya panatilihin na sa isip. 

At sa klase na ito, kami ay karaniwang pagpunta upang iwanan ang mahigpit na pagtatasa sa isang tabi. May mga agham at mga patlang mapagmahal sa ganitong uri ng bagay-bagay. Kapag ang usapan namin tungkol sa pangangatwiran sa pamamagitan ng mga algorithm, na kung saan kami ay gawin piraso-by-piraso para sa maraming algorithms usapan namin sa klase. Kami ay talagang pakikipag-usap tungkol pangangatwiran sa pamamagitan nito na may bait, Hindi na may mga formula, o mga katibayan, o anumang bagay na tulad ng. Kaya huwag mag-alala, hindi namin ay magiging nagiging sa isang malaking klase ng math. 

Kaya sinabi ko pinapahalagahan namin tungkol sa pagiging kumplikado dahil ito ay humihingi ng mga katanungan, kung paano huwag aming mga algorithm hawakan mas malaki at mas malaking hanay ng data hagis sa kanila. Well, kung ano ang isang set ng data? Ano ang ibig sabihin ko kapag sinabi ko na? Ito ay nangangahulugan na ang anumang gumagawa ng pinaka kahulugan sa konteksto, upang maging matapat. Kung kami ay may isang algorithm, ang Proseso Strings-- hindi namin marahil pakikipag-usap tungkol sa laki ng mga string. Iyan ay ang data set-- ang laki, ang bilang ng mga character na bumubuo sa string. Kung pinag-uusapan natin ang tungkol sa isang algorithm na ang proseso ng file, maaaring pakikipag-usap namin tungkol sa kung paano maraming kilobytes masaklaw na file. At iyan ang set ng data. Kung pinag-uusapan natin ang tungkol sa isang algorithm na humahawak sa mga array mas pangkalahatang paraan, tulad ng pag-uuri algorithm o naghahanap algorithm, marahil kami ay pakikipag-usap tungkol sa bilang ng mga elemento na bumubuo ng isang array. 

Ngayon, maaari naming sukatin ang isang algorithm-- sa partikular, kapag sinasabi ko makakaya namin sukatin ang isang algorithm, ako ibig sabihin maaari naming masukat kung gaano maraming mga mapagkukunan na aabutin up. Kung ang mga resources ay, kung gaano karaming bytes ng RAM-- o megabytes ng RAM ginagamit nito. O kung magkano ang panahon na kailangan upang tumakbo. At maaari naming tawagan ang masukat, nagkataon, f ng n. Saan ang n ay ang bilang ng mga mga elemento sa hanay ng data. At f ng n ay kung gaano karaming mga somethings. Gaano karaming mga unit ng mga mapagkukunan ay ito ay nangangailangan upang i-proseso ang data na iyon. 

Ngayon, namin talagang hindi pag-aalaga tungkol sa kung ano f ng n ay eksakto. Sa katunayan, napaka-bihira namin will-- tiyak ay hindi na ito sa class-- ko sumisid sa anumang talagang malalim pagtatasa ng kung ano f ng n ay. Kami ay pagpunta sa makipag-usap tungkol sa kung ano f ng n ay humigit-kumulang o kung ano ito ay may gawi na. At ang mga ugali ng isang algorithm ay idinidikta ng kanyang pinakamataas na kataga order. At maaari naming makita kung ano ang aking ibig sabihin sa pamamagitan ng na sa pamamagitan ng pagsasagawa isang tumingin sa isang mas kongkreto halimbawa. 

Kaya sabihin natin na mayroon kami tatlong iba't-ibang mga algorithm. Ang unang na kung saan tumatagal ng n nakakubo, ang ilang mga yunit ng mga mapagkukunan upang i-proseso ang isang hanay ng mga laki n data. Kami ay may isang pangalawang algorithm na tumatagal n nakakubo plus n nakalapat mapagkukunan upang i-proseso ang isang hanay ng mga laki n data. At kami ay may isang ikatlong algorithm na tumatakbo in-- na tumatagal ng hanggang n nakakubo minus 8n nakalapat plus 20 n dami ng kayamanan upang i-proseso ang isang algorithm may data set ng size n. 

Ngayon muli, talagang hindi namin ay pagpunta upang makakuha ng sa antas na ito ng detalye. Talagang ako lang ay ang mga up dito bilang isang paglalarawan ng isang punto na pupuntahan ko na maging paggawa sa isang segundo, na kung saan ay na lamang talagang pakialam namin tungkol sa mga ugali ng mga bagay-bagay bilang makakuha ng mas malaki ang mga hanay ng data. Kaya kung ang hanay ng data ay maliit, may talagang isang medyo malaking pagkakaiba sa mga algorithm. Ang ikatlong algorithm doon tumatagal ng 13 beses na, 13 beses ang dami ng mga mapagkukunan upang magpatakbo ng kamag-anak sa una. 

Kung ang aming data set ay size 10, na ay mas malaki, ngunit hindi kinakailangan na malaki, maaari naming makita na mayroong talagang isang piraso ng isang pagkakaiba. Ang ikatlong algorithm nagiging mas mahusay. Ito ay tungkol sa aktwal na 40% - o 60% mas mahusay. Ito ay tumatagal ng 40% ng halaga ng oras. Maaari itong run-- maaari itong tumagal 400 mga yunit ng mga mapagkukunan upang i-proseso ang isang hanay ng size 10 data. Sapagkat ang unang algorithm, sa pamamagitan ng kaibahan, tumatagal ng 1,000 yunit ng mga mapagkukunan upang i-proseso ang isang hanay ng size 10 data. Ngunit tumingin kung ano ang mangyayari bilang ang aming mga numero na nakukuha kahit na mas malaki. 

Ngayon, ang pagkakaiba sa pagitan ng mga algorithm magsisimula na maging isang maliit na mas maliwanag. At ang mga katotohanan na may mga mas mababang-order terms-- o sa halip, mga tuntunin na may mas mababang exponents-- simulan upang maging kaugnay. Kung ang isang hanay ng data ay ng laki 1000 at ang unang algorithm ay tumatakbo sa isang bilyong mga hakbang. At ang pangalawang algorithm ay tumatakbo sa isang bilyon at isang milyong mga hakbang. At tumatakbo ang ikatlong algorithm sa nahihiya lamang ng isang bilyong mga hakbang. Ito ay medyo marami ang isang bilyong mga hakbang. Simulan mga tuntunin ng mas mababang-order upang maging tunay na kaugnay. At lamang sa tunay martilyo sa bahay ang point-- kung ang input ng data ay ang laki ng isang million-- lahat ng tatlong mga medyo marami kumuha ng isa quintillion-- kung aking matematika ay correct-- hakbang upang i-proseso ang isang input ng data ng laki ng isang milyon. Iyan ay isang pulutong ng mga hakbang. At ang katunayan na ang isa sa kanila baka tumagal ng ilang 100,000, o isang pares ng 100 million kahit na mas mababa kapag pinag-uusapan natin ang tungkol sa isang bilang na big-- ito ay uri ng hindi kaugnay na. Lahat sila ay may posibilidad na gumawa humigit-kumulang n nakakubo, at sa gayon kami ay tunay na sumangguni sa lahat ng mga algorithm bilang sa pagkakasunod-sunod ng n nakakubo o malaki-O ng n nakakubo. 

Narito ang isang listahan ng ilan sa mga mas karaniwang computational kumplikado klase na makikita namin nakakaharap sa algorithms, sa pangkalahatan. At din partikular sa CS50. Ang mga ito ay iniutos mula sa pangkalahatan pinakamabilis sa itaas, sa pangkalahatan ay pinakamabagal sa ilalim. Kaya pare-pareho ang oras algorithm madalas na ang pinakamabilis na, hindi alintana ang laki ng input data pumasa ka sa. Lagi silang kumuha ng isang operasyon o isang yunit ng mga mapagkukunan upang harapin. Ito ay maaaring maging 2, kapangyarihan ito magiging 3, maaaring ito ay 4. Ngunit ito ay isang constant number. Hindi ito nag-iiba. 

Logarithmic time algorithms bahagyang mas mahusay. At isang tunay na magandang halimbawa ng isang logarithmic oras algorithm tiyak na iyong nakikita sa pamamagitan ng ngayon ay ang pansiwang bukod ng phone book upang mahanap Mike Smith sa aklat ng telepono. Cut namin ang problema sa kalahati. At gayon n makakakuha ng mas malaki at mas malaki at larger-- sa katunayan, ang bawat oras mong i-double n, tatagal lamang ito ng isa pang hakbang. Kaya na ng maraming mas mahusay sa, sabihin nating, sa haba ng panahon. Alin ang kung double ka n, ito tumatagal ng double ang bilang ng mga hakbang. Kung ikaw triple n, ito ay tumatagal ng triple ang bilang ng mga hakbang. Isang hakbang sa bawat unit. 

Pagkatapos bagay makakuha ng isang maliit more-- mas mababa maliit na mahusay na mula doon. Mayroon kang linear rhythmic oras, minsan tinatawag na haba ng panahon log o lamang n log n. At bibigyan namin ng isang halimbawa ng isang algorithm na tumatakbo sa n log n, na kung saan ay mas mahusay pa rin kaysa sa parisukat time-- n nakalapat. O polinomyal oras, n dalawang ng anumang numero na mas malaki kaysa sa dalawa. O pagpaparami oras, na ay kahit worse-- C sa n. Kaya ang ilang mga tapat na numero itataas sa ang kapangyarihan ng laki ng input. Kaya kung may 1,000-- kung ang input data ay sukat ng 1000, ito ay tumagal ng C sa 1000 power. Ito ay isang pulutong mas masahol pa kaysa polinomyal oras. 

Factorial time ay kahit na mas masahol pa. At sa katunayan, may tunay gawin umiiral walang katapusan na oras algorithm, tulad ng, tinatawag tangang sort-- na trabaho ay upang random shuffle isang array at pagkatapos ay suriin upang makita kung ito ay pinagsunod-sunod. At kung ito ay hindi, sapalaran kaladkarin ang mga paa muli ang array at suriin upang makita kung ito ay pinagsunod-sunod. At bilang maaari mong marahil imagine-- maaari mong isipin ang isang sitwasyon kung saan sa pinakamasama-case, na kalooban hindi aktwal na magsimula sa mga array. Algorithm na nais tumakbo magpakailanman. At sa gayon ay magiging isang walang katapusan na oras algorithm. Sana hindi mo ay sumusulat anumang factorial o walang katapusan na oras algorithm sa CS50. 

Kaya, sabihin kumuha ng isang maliit na mas kongkreto pagtingin sa ilan sa mas simple computational kumplikado klase. Kaya mayroon kaming isang example-- o dalawang halimbawa here-- ng pare-pareho ang oras algorithm, na laging dalhin isang operasyon sa pinakamasama-case. Kaya ang unang example-- kami ay may isang function tinatawag 4 para sa iyo, na tumatagal ng isang hanay ng mga laki 1,000. Ngunit pagkatapos ay tila ay hindi aktwal na hitsura sa ay hindi talagang pakialam it-- kung ano ang sa loob ng mga ito, sa na array. Laging nagbabalik lamang ng apat. Kaya, algorithm na iyon, sa kabila ng katotohanan na ito tumatagal ng 1,000 mga elemento ay hindi ay gumawa ng anumang bagay sa kanila. Nagbabalik apat lamang. Ito ay palaging isang solong hakbang. 

Sa katunayan, magdagdag ng 2 nums-- saan na nakita natin dati bilang well-- Pinoproseso lamang ng dalawang integer. Ito ay hindi isang solong hakbang. Ito ay talagang isang pares na mga hakbang. Makakakuha ka ng isang, ikaw ay makakuha ng b, idagdag mo ang mga ito sama-sama, at ikaw output ang mga resulta. Kaya ito ay 84 na hakbang. Ngunit ito ay palaging tapat, hindi alintana ng isa o b. Mayroon kang makakuha ng, makakuha b, magdagdag ang mga ito nang sama-sama, output ang mga resulta. Kaya na ang isang pare-pareho ang oras algorithm. 

Narito ang isang halimbawa ng isang sa haba ng panahon algorithm-- isang algorithm na gets-- na tumatagal isang karagdagang hakbang, marahil, habang lumalaki ang iyong input sa pamamagitan ng 1. Kaya, sabihin natin na kaming naghahanap ng mga ang bilang 5 sa loob ng isang array. Maaari mong magkaroon ng isang sitwasyon kung saan maaari mong mahanap ito medyo maaga. Ngunit maaari mo ring magkaroon ng isang sitwasyon kung saan ito ay maaaring ang huling element ng array. Sa isang hanay ng mga laki 5, kung kami ay naghahanap para sa mga numero ng 5. Gusto tumagal ng 5 hakbang. At sa katunayan, isipin na may hindi 5 kahit saan sa array na ito. Kami pa rin ang tunay na may upang tumingin sa bawat isang elemento ng array upang matukoy kung o hindi 5 ay doon. 

Kaya sa pinakamasama-case, na kung saan ay na ang elemento ay huling sa array o hindi umiiral sa lahat. Mayroon pa kaming upang tumingin sa lahat ng mga n elemento. At kaya ito algorithm tumatakbo sa haba ng panahon. Maaari mong kumpirmahin na sa pamamagitan ng extrapolating nang kaunti sa pagsasabing, kung nagkaroon kami ng array 6-elemento at humahanap kami ng mga number 5, maaari itong tumagal ng 6 na mga hakbang. Kung kami ay may isang array 7-elemento at kami ay naghahanap para sa mga numero ng 5. Maaaring tumagal ng 7 mga hakbang. Habang nagdadagdag kami ng isa pang elemento sa aming array, ito ay tumatagal ng isa pang hakbang. Iyan ay isang linear algorithm sa pinakamalala-case. 

Ilang mabilis na mga katanungan para sa iyo. Ano ang runtime-- kung ano ang ang pinakamasama-case runtime ng mga ito partikular na snippet ng code? Kaya ako ng isang 4 loop dito na tumatakbo mula j katumbas ng 0, ang lahat ng mga paraan ng hanggang sa m. At kung ano ang ko na nakikita dito, ay na ang mga katawan ng loop tumatakbo sa tapat na oras. Kaya gamit ang mga terminolohiya na na pinag-usapan namin na about-- ano ay ang pinakamasama-case runtime ng algorithm na ito? Kumuha ng isang segundo. Ang panloob na bahagi ng loop tumatakbo sa tapat na oras. At ang mga panlabas na bahagi ng loop ang magpapatakbo ng beses m. Kaya kung ano ang pinakamasama-case runtime dito? Hulaan mo ba big-O ng m? Gusto mong maging tama. 

Paano ang tungkol sa isa pa? Oras na ito kami ay may isang loop sa loob ng isang loop. Kami ay may isang panlabas na loop na tumatakbo mula sa zero sa p. At kami ay may isang panloob na loop na tumatakbo mula sa zero sa p, at sa loob ng na, Estado ko na ang katawan ng loop tumatakbo sa tapat na oras. Kaya kung ano ang pinakamasama-case runtime ng mga ito partikular na snippet ng code? Well, muli, kami ay may isang panlabas na loop na tumatakbo ulit p. At sa bawat pag-ulit time-- ng na loop, sa halip. Mayroon kaming isang panloob na loop na din ang nagpapatakbo ng beses p. At pagkatapos ay sa loob ng na, may mga constant time-- kaunti doon snippet. 

Kaya kung kami ay may isang panlabas na loop na tumatakbo beses p sa loob ng kung saan ay sa loob ng isang loop na tumatakbo p times-- kung ano ang ang pinakamasama-case runtime ng ang snippet ng code? Hulaan mo ba big-O ng p nakalapat? 

Ako Doug Lloyd. Ito ay CS50.