Mae pob hawl, felly, cymhlethdod cyfrifiadurol. Dim ond ychydig o rybudd cyn i ni plymio yn rhy far-- Mae'n debyg y byddwch hyn fod ymysg pethau mwyaf mathemateg-trwm rydym yn siarad am yn CS50. Gobeithio na fydd yn rhy llethol a byddwn yn ceisio eich tywys drwy'r broses, ond dim ond ychydig o rybudd teg. Mae ychydig bach o mathemateg dan sylw yma. Mae pob hawl, felly er mwyn gwneud defnydd o'n hadnoddau cyfrifiadurol yn y world-- go iawn 'i' 'n sylweddol bwysig deall algorithmau a sut y maent yn prosesu data. Os oes gennym mewn gwirionedd algorithm effeithlon, rydym yn Gall lleihau faint o adnoddau sydd ar gael gennym i ddelio ag ef. Os oes gennym algorithm sy'n yn mynd i gymryd llawer o waith i brosesu 'n sylweddol set fawr o ddata, mae'n mynd i angen mwy a mwy o adnoddau, a oedd yn arian, RAM, pob math hwnnw o bethau yn. 

Felly, y gallu i ddadansoddi yn algorithm gan ddefnyddio'r offeryn hwn set, yn y bôn, yn gofyn i'r question-- sut mae graddfa algorithm hwn wrth i ni daflu mwy a mwy o ddata arno? Yn CS50, faint o ddata rydym yn gweithio gyda yn eithaf bach. Yn gyffredinol, mae ein rhaglenni yn mynd i redeg mewn ail neu less-- yn ôl pob tebyg yn llawer llai yn enwedig yn gynnar. 

Ond meddyliwch am gwmni sy'n delio gyda channoedd o filiynau o gwsmeriaid. Ac mae angen i brosesu hynny data cwsmeriaid. Gan fod nifer y cwsmeriaid y maent yn wedi mynd yn fwy ac yn fwy, mae'n mynd i'w gwneud yn ofynnol mwy a mwy o adnoddau. Faint mwy o adnoddau? Wel, mae hynny'n dibynnu ar ba mor byddwn yn ddadansoddi y algorithm, defnyddio'r offer yn y blwch offer hwn. Pan fyddwn yn sôn am gymhlethdod mae algorithm-- sydd weithiau'n wnewch chi helpu glywed y cyfeirir ato fel amser cymhlethdod neu le gymhlethdod ond rydym yn jyst yn mynd i alw complexity-- rydym yn gyffredinol yn siarad am y sefyllfa waethaf. O ystyried y absoliwt pentwr gwaethaf o data y gallem fod yn taflu arno, sut mae algorithm hwn yn mynd i prosesu neu ddelio â data hwnnw? Rydym yn gyffredinol yn galw y gwaethaf-achos Rhedeg o algorithm mawr-O. Felly efallai y algorithm yn cael ei dweud i rhedeg mewn O n neu O n sgwâr. A mwy am yr hyn y y rhai yn ei olygu mewn eiliad. 

Weithiau, fodd bynnag, rydym yn ei wneud gofal am y sefyllfa orau-achos. Os yw'r data yn bopeth yr oeddem am iddo fod ac yr oedd yn hollol berffaith ac yr oeddem yn anfon hwn perffaith set o ddata trwy ein algorithm. Sut y byddai'n trin yn y sefyllfa honno? Weithiau, rydym yn cyfeirio at hynny fel mawr-Omega, felly yn wahanol i fawr-O, mae gennym fawr-Omega. Big-Omega ar gyfer y sefyllfa orau-achos. Big O-gyfer y sefyllfa waethaf. Yn gyffredinol, pan fyddwn yn sôn am cymhlethdod algorithm, rydym yn sôn am y sefyllfa waethaf. Felly cadwch hynny mewn cof. 

Ac yn y dosbarth hwn, rydym yn mynd yn gyffredinol i adael y dadansoddiad trylwyr o'r neilltu. Mae gwyddorau a chaeau neilltuo i math hwn o bethau. Pan fyddwn yn sôn am rhesymu trwy algorithmau, y byddwn yn ei wneud darn-by-darn ar gyfer llawer algorithmau rydym yn siarad am yn y dosbarth. Rydym yn wir yn unig yn siarad am rhesymu drwyddo gyda synnwyr cyffredin, nid gyda fformiwlâu, neu proflenni, neu unrhyw beth fel 'na. Felly peidiwch â phoeni, ni fyddwn yn droi i mewn i ddosbarth mathemateg mawr. 

Felly yr wyf yn dweud ein bod yn poeni am gymhlethdod oherwydd ei fod yn gofyn y cwestiwn, sut mae ein algorithmau trin mwy o faint a setiau data mwy o faint yn cael eu taflu atynt. Wel, beth yw set ddata? Beth wnes i ei olygu pan ddywedais hynny? Mae'n golygu beth bynnag yn gwneud y mwyaf synnwyr mewn cyd-destun, a bod yn onest. Os oes gennym algorithm, y Prosesau Strings-- rydym yn ôl pob tebyg siarad am faint y llinyn. Dyna y data set-- maint, mae nifer o gymeriadau sy'n rhan o'r llinyn. Os ydym yn sôn am algorithm sy'n prosesu ffeiliau, Efallai y byddwn yn sôn am sut llawer o kilobytes yn cynnwys y ffeil. A dyna y set ddata. Os ydym yn sôn am algorithm sy'n delio araeau yn fwy cyffredinol, fel algorithmau didoli neu chwilio algorithmau, yn ôl pob tebyg rydym yn sôn am y nifer o elfennau sy'n cynnwys amrywiaeth. 

Yn awr, gallwn fesur yn algorithm-- yn arbennig, wrth ddweud y gallwn mesur algorithm, yr wyf yn yn golygu y gallwn fesur pa mor llawer o adnoddau y mae'n ei gymryd i fyny. P'un adnoddau hynny yw, faint o bytes o RAM-- neu megabeit o RAM mae'n defnyddio. Neu faint o amser mae'n ei gymryd i redeg. A gall rydym yn galw hyn mesur, fympwyol, f o n. Pan n yw nifer y elfennau yn y set ddata. A f o n yw faint o somethings. Sawl uned o adnoddau yn mae'n ei gwneud yn ofynnol i brosesu data hynny. 

Nawr, nid ydym mewn gwirionedd yn poeni am yr hyn y f o n yn union. Yn wir, rydym yn anaml iawn will-- yn sicr y bydd byth yn y wyf class-- plymio i mewn i unrhyw 'n sylweddol dwfn dadansoddiad o beth f o n yn. Rydym yn jyst yn mynd i siarad am yr hyn f o n tua neu'r hyn mae'n tueddu i. Ac mae'r duedd o algorithm yw bennu gan ei dymor radd uchaf. A gallwn weld yr hyn yr wyf olygu wrth hynny drwy gymryd a edrych ar enghraifft yn fwy pendant. 

Felly, gadewch i ni ddweud ein bod wedi tri algorithmau gwahanol. Y cyntaf ohonynt yn cymryd n giwbiau, mae rhai unedau o adnoddau i brosesu set ddata o faint n. Mae gennym ail algorithm sy'n cymryd n torri'n giwbiau ac adnoddau n sgwâr i brosesu set ddata o faint n. Ac mae gennym traean algorithm sy'n rhedeg in-- hynny cymryd n 8n minws wedi'i dorri'n giwbiau sgwâr yn ogystal â 20 o unedau n adnoddau i brosesu algorithm gyda data a osodir o faint n. 

Nawr eto, yr ydym ddim wir yn mynd i fynd i mewn y lefel hon o fanylder. Im 'mewn gwirionedd dim ond gael y rhain i fyny yma fel enghraifft o bwynt fy mod i'n mynd i fod yn gwneud mewn eiliad, a oedd yw ein bod dim ond 'n sylweddol gofal am y duedd o bethau gan fod y setiau data yn cynyddu. Felly, os yw'r set ddata yn fach, mae ' mewn gwirionedd gwahaniaeth eithaf mawr yn y algorithmau hyn. Mae'r trydydd algorithm yno yn cymryd 13 gwaith yn hirach, 13 gwaith y swm o adnoddau i redeg o'i gymharu â'r un cyntaf. 

Os yw ein set ddata yw maint 10, sy'n yn fwy, ond nid o reidrwydd enfawr, gallwn weld bod yna mewn gwirionedd yn dipyn o wahaniaeth. Mae'r trydydd algorithm yn dod yn fwy effeithlon. Mae'n ymwneud â gwirionedd 40% - neu 60% yn fwy effeithlon. Mae'n cymryd 40% faint o amser. Gall run-- gall gymryd 400 o unedau o adnoddau i brosesu set ddata o faint 10. Tra bod y cyntaf algorithm, mewn cyferbyniad, yn cymryd 1,000 o unedau o adnoddau i brosesu set ddata o faint 10. Ond edrychwch beth sy'n digwydd fel ein rhifau gael hyd yn oed yn fwy. 

Yn awr, mae'r gwahaniaeth rhwng y algorithmau hyn dechrau dod ychydig yn llai amlwg. Ac mae'r ffaith bod yna is-archebu terms-- neu yn hytrach, delerau â exponents-- is dechrau dod yn amherthnasol. Os set ddata o faint 1,000 a'r algorithm cyntaf yn rhedeg mewn biliwn o gamau. A'r ail algorithm yn rhedeg mewn camau biliwn a miliwn. A'r trydydd algorithm yn rhedeg mewn dim ond yn swil o biliwn o gamau. Mae'n 'n bert lawer biliwn o gamau. Mae'r rhai termau is-archebu cychwyn i fod yn wir yn amherthnasol. A dim ond i wir morthwyl gartref y point-- os yw'r mewnbynnu data o faint a million-- pob un o'r tri o'r rhain yn 'n bert lawer cymryd un quintillion-- os fy mathemateg yn gamau correct-- i brosesu data a fewnbynnir o faint miliwn. Mae hynny'n llawer o risiau. Ac mae'r ffaith bod un ohonynt efallai yn cymryd ychydig 100,000, neu gwpl 100 miliwn hyd yn oed yn llai pan rydym yn sôn am nifer hynny big-- mae'n fath o amherthnasol. Maent i gyd yn tueddu i gymryd tua n giwbiau, ac felly byddem yn mewn gwirionedd yn cyfeirio i bob un o'r algorithmau hyn fel bod ar y drefn n torri'n giwbiau neu fawr-O n dorri'n giwbiau. 

Dyma restr o rai o'r mwy dosbarthiadau cymhlethdod cyfrifiadurol cyffredin y byddwn yn dod ar eu traws mewn algorithmau, yn gyffredinol. A hefyd yn benodol mewn CS50. Mae'r rhain yn cael eu harchebu gan Yn gyffredinol gyflymaf ar y brig, i yn gyffredinol arafaf ar y gwaelod. Felly algorithmau amser cyson yn tueddu i fod y cyflymaf, beth bynnag o faint y mewnbynnu data i chi basio i mewn. Maent bob amser yn cymryd un llawdriniaeth neu un uned o adnoddau i ddelio ag ef. Gallai fod yn 2, y gallai fod yn 3, gallai fod yn 4. Ond mae'n rhif gyson. Nid yw'n amrywio. 

Algorithmau amser logarithmig ychydig yn well. Ac yn enghraifft dda iawn o algorithm amser logarithmig eich bod wedi gweld yn sicr erbyn hyn yw'r rhwygo ar wahân y llyfr ffôn i ddod o hyd Mike Smith yn y llyfr ffôn. Rydym yn torri y broblem yn ei hanner. Ac felly fel n mynd yn fwy a mwy o faint a larger-- mewn gwirionedd, bob tro y byddwch yn dyblu n, dim ond yn cymryd un cam mwy. Felly dyna yn llawer gwell na, dyweder, amser llinol. Pa un yw os ydych yn dyblu n, mae'n cymryd dwbl y nifer o gamau. Os byddwch yn triphlyg n, mae'n cymryd dreblu nifer o gamau. Un cam yr uned. 

Yna pethau'n mynd ychydig o more-- ychydig yn llai gwych oddi yno. Mae gennych amser rhythmig llinol, weithiau Gelwir log amser llinol neu dim ond n log n. Ac rydym chi helpu enghraifft o algorithm sy'n yn rhedeg yn n log n, sydd yn dal yn well na cwadratig adeg-- n sgwâr. Neu amser polynomial, n dau unrhyw nifer fwy na dau. Neu amser esbonyddol, a oedd yn hyd yn oed yn worse-- C i'r n. Felly mae rhai rhif gyson codi i grym maint y mewnbwn. Felly, os oes 1,000-- os bydd y mewnbynnu data o faint 1,000, byddai'n cymryd C i'r pŵer 1,000fed. Mae'n llawer gwaeth nag amser polynomial. 

Amser ffactoraidd yn oed yn waeth. Ac yn wir, mae yna wir yn bodoli algorithmau amser anfeidrol, megis, hyn a elwir yn sort-- dwp y mae ei swydd yw siffrwd arae ar hap ac yna edrychwch i weld a boed yn datrys. Ac os nad yw'n, ar hap siffrwd y rhesi eto a gwirio i weld a yw'n datrys. Ac fel y mae'n debyg y gallwch imagine-- gallwch ddychmygu sefyllfa ble yn y gwaethaf-achos, bydd hynny byth mewn gwirionedd yn dechrau gyda y rhesi. Byddai hynny'n algorithm rhedeg am byth. Ac felly byddai hynny'n algorithm amser anfeidrol. Gobeithio na fyddwch yn ysgrifennu unrhyw adeg ffactoraidd neu anfeidrol algorithmau yn CS50. 

Felly, gadewch i ni gymryd ychydig yn fwy Golwg concrit ar rai symlach dosbarthiadau cymhlethdod cyfrifiadurol. Felly mae gennym example-- neu ddwy enghraifft Yma-- o algorithmau amser cyson, sydd bob amser yn cymryd llawdriniaeth sengl yn y gwaethaf-achos. Felly, y example-- cyntaf mae gennym swyddogaeth Gelwir 4 ar eich cyfer, a oedd yn yn cymryd amrywiaeth o faint 1,000. Ond yna mae'n debyg nid yw'n edrych mewn gwirionedd nid yn iddo-- ddim wir yn poeni beth sydd tu mewn iddo, o'r rhesi. Bob amser yn unig yn dychwelyd pedwar. Felly, y algorithm, er gwaethaf y ffaith ei fod yn yn cymryd 1,000 o elfennau nad yw'n gwneud unrhyw beth gyda nhw. Dim ond yn dychwelyd pedwar. Mae bob amser un cam. 

Yn wir, ychwanegwch 2 nums-- sy'n rydym wedi gweld o'r blaen fel well-- dim ond prosesau dau rif cyfan. Nid yw'n un cam. Mae'n mewn gwirionedd camau cwpl. Byddwch yn cael, byddwch yn cael b, rydych yn eu hychwanegu gyda'i gilydd, ac yr ydych allbwn y canlyniadau. Felly mae'n 84 cam. Ond mae'n gyson bob amser, waeth beth a neu b. Mae'n rhaid i chi gael, yn cael b, ychwanegu nhw at ei gilydd, allbwn y canlyniad. Felly dyna algorithm amser cyson. 

Dyma enghraifft o algorithm-- amser llinol algorithm sy'n gets-- sy'n cymryd un cam ychwanegol, o bosibl, fel eich mewnbwn yn tyfu gan 1. Felly, gadewch i ni ddweud ein bod yn chwilio am rhif 5 tu mewn arae. Efallai y bydd gennych sefyllfa lle gallwch ddod o hyd iddo yn weddol gynnar. Ond gallech hefyd gael sefyllfa lle y mae'n Efallai fod yr elfen olaf y rhesi. Mewn amrywiaeth o faint 5, os rydym yn chwilio am y rhif 5. Byddai'n cymryd 5 cam. Ac yn wir, ddychmygu bod yna Nid yw 5 yn unrhyw le yn amrywiaeth hwn. Mae gennym mewn gwirionedd yn edrych ar pob elfen unigol y rhesi er mwyn penderfynu ai peidio 5 yno. 

Felly, yn y-achos gwaethaf, sef bod yr elfen hon yn olaf yn y casgliad neu os nad yw'n bodoli o gwbl. Rydym yn dal i orfod edrych ar pob un o'r elfennau n. Ac felly algorithm hwn yn rhedeg mewn amser llinol. Gallwch gadarnhau bod gan allosod ychydig drwy ddweud, pe bai gennym 6-elfen amrywiaeth a roeddem yn chwilio am y rhif 5, gall gymryd 6 cham. Os oes gennym 7-elfen amrywiaeth a rydym yn chwilio am y rhif 5. Gallai gymryd 7 cam. Wrth i ni ychwanegu un elfen fwy at ein array, mae'n cymryd un cam mwy. Dyna algorithm llinol yn y gwaethaf-achos. 

Cwpl gwestiynau cyflym i chi. Beth yw'r runtime-- beth sy'n yr-achos gwaethaf runtime o hyn snippet arbennig o god? Felly mae gen i ddolen 4 yma sy'n rhedeg o j yn dychwelyd 0, yr holl ffordd i fyny at m. A beth dw i'n gweld yma, yw bod y corff y ddolen yn rhedeg mewn amser cyson. Felly ddefnyddio'r derminoleg y rydym eisoes wedi siarad about-- beth fyddai y gwaethaf-achos Rhedeg yr algorithm hwn? Cymerwch eiliad. Mae'r rhan fewnol y ddolen yn rhedeg mewn amser cyson. A'r rhan allanol y ddolen yn mynd i redeg amseroedd m. Felly beth yw'r Rhedeg waethaf yma? A wnaethoch chi ddyfalu fawr-O o'r m? Byddech yn iawn. 

Beth am un arall? Y tro hwn mae gennym dolen tu mewn dolen. Mae gennym dolen allanol sy'n rhedeg o sero i t. Ac mae gennym dolen mewnol sy'n rhedeg o sero i p, ac y tu mewn o hynny, Yr wyf yn datgan bod y corff y ddolen yn rhedeg mewn amser cyson. Felly beth yw'r Rhedeg gwaethaf-achos o hyn snippet arbennig o god? Wel, unwaith eto, mae gennym dolen allanol sy'n rhedeg amseroedd t. A phob iteriad adeg-- o'r ddolen, yn hytrach. Mae gennym dolen mewnol hynny hefyd yn rhedeg amseroedd t. Ac yna y tu mewn o hynny, mae y snippet bach adeg-- cyson yno. 

Felly, os oes gennym dolen allanol sy'n yn rhedeg amseroedd p tu mewn sydd yn dolen mewnol sy'n rhedeg p times-- hyn sy'n yr-achos gwaethaf runtime o snippet hon o god? A wnaethoch chi ddyfalu fawr-O o p sgwâr? 

Rwy'n Doug Lloyd. Mae hyn yn CS50.