Molt bé, així, la complexitat computacional. Només una mica d'un advertiment Abans d'aprofundir en massa far-- això probablement serà entre les coses més pesat de matemàtiques parlem en CS50. Esperem que no sigui massa aclaparador i anem a tractar de guiar a través del procés, però només una mica d'una advertència justa. Hi ha una mica de matemàtiques involucrades aquí. D'acord, amb la finalitat de fer ús dels nostres recursos computacionals en el real món-- és realment important entendre algoritmes i com es processen les dades. Si tenim una realitat algoritme eficient, ens pot reduir al mínim la quantitat de recursos que tenim disponible per tractar amb ell. Si tenim un algoritme que es va a prendre un munt de treball per processar una realitat gran conjunt de dades, és requerirà més i més recursos, que són els diners, la memòria RAM, tot aquest tipus de coses. 

Per tant, ser capaç d'analitzar una algoritme que utilitza aquest conjunt d'eines, bàsicament, es pregunta el pregunta-- Com funciona aquesta escala algoritme com tirem més i més dades en ell? En CS50, la quantitat de dades que estem treballar amb és bastant petita. En general, els nostres programes van per executar-se en un segon o less-- probablement molt menys sobretot des del principi. 

Però pensa en una empresa que ofertes amb centenars de milions de clients. I necessiten per processar que les dades del client. A mesura que el nombre de clients als quals tenen fa més gran i més gran, que requerirà més i més recursos. Quants més recursos? Bé, això depèn de com analitzem l'algorisme, utilitzant les eines d'aquesta caixa d'eines. Quan parlem de la complexitat de 1 algorithm-- que de vegades hauràs escoltar la seva pronunciació coneix com a temps complexitat o espai complexitat però només anem cridar complexity-- estem parlant en general, el pitjor dels casos. Tenint en compte el pitjor pila absoluta dades que podríem estar llançant en ell, com es va a aquest algoritme processar o tractar amb aquestes dades? En general, anomenem el pitjor dels casos temps d'execució d'un algoritme gran-O. Així que un algoritme podria dir-se que executar a O de n o O de n al quadrat. I més del que aquells vol dir en un segon. 

A vegades, però, ens importa sobre el millor dels casos. Si les dades són tot el que volíem que sigui i que era absolutament perfecte i estàvem enviant aquesta perfecta un conjunt de dades a través del nostre algorisme. Com seria gestionar en aquesta situació? A vegades ens referim al fet que a mesura big-Omega, de manera que en contrast amb la gran-O, tenim grans Omega. Big-Omega per el millor dels casos. Big-O per al pitjor dels casos. Generalment, quan es parla de la complexitat d'un algorisme, estem parlant de la pitjor dels casos. Així que tingues-ho en compte. 

I en aquesta classe, estem generalment va per deixar l'anàlisi rigorosa de costat. Hi ha ciències i camps dedicat a aquest tipus de coses. Quan parlem de raonament a través d'algoritmes, que farem peça per peça per a molts algoritmes que ens parlen de la classe. Realment estem parlant només de raonament a través d'ell amb el sentit comú, no amb fórmules, o proves, ni res d'això. Així que no es preocupi, nosaltres no serem convertint-se en una classe de matemàtiques gran. 

Així que li vaig dir que ens preocupem per la complexitat perquè fa la pregunta, com no manegen els nostres algoritmes més gran i grans conjunts de dades que són llançats contra ells. Bé, el que és un conjunt de dades? Què vaig voler dir quan vaig dir això? Significa ho aprofita al màxim sentit en el context, per ser honest. Si tenim un algoritme, el Processos Strings-- estem probablement parlant sobre la mida de la cadena. Això és les dades definido-- la mida, el nombre de caràcters que componen la cadena. Si estem parlant d'un algoritme que processa els arxius, podríem estar parlant de com molts kilobytes comprenen aquest arxiu. I aquest és el conjunt de dades. Si estem parlant d'un algoritme que maneja arrays de manera més general, tals com algoritmes d'ordenació o la recerca d'algoritmes, probablement estem parlant de la sèrie dels elements que conformen una matriu. 

Ara, podem mesurar una algorithm-- en particular, quan dic que podem mesuro un algoritme, que vol dir que podem mesurar la molts recursos que ocupa. Ja sigui que aquests recursos són, quants bytes de RAM-- o megabytes de RAM que utilitza. O quant de temps es triga a executar. I podem cridar a això mesurar, de manera arbitrària, f de n. On n és el nombre de elements en el conjunt de dades. I f de n és el nombre de tants. Quantes unitats de recursos fa es requereix per processar aquestes dades. 

Ara, en realitat no ens importa sobre el que f de n és exactament. De fet, molt rarament voluntat-- sens dubte mai es en aquest class-- I bussejar en qualsevol realment profund anàlisi del que f de n és. Només anem a parlar del f de n és d'aproximadament o el que tendeix a. I la tendència d'un algoritme és dictat pel seu terme més alt ordre. I podem veure el que dir amb que en prendre Una mirada a un exemple més concret. 

Així que anem a dir que tenim tres algorismes diferents. El primer dels quals té n cubs, algunes unitats de recursos per processar un conjunt de dades de grandària n. Tenim un segon algorisme que pren n cubs més recursos n al quadrat per processar un conjunt de dades de grandària n. I tenim una tercera algoritme que s'executa en-- que ocupa n 8n menys a la galleda quadrat més 20 n unitats de recursos per processar un algoritme amb conjunt de grandària n de dades. 

Ara, de nou, que realment no anem per entrar en aquest nivell de detall. Estic realment només tinc aquestes dalt aquí com una il·lustració d'un punt que jo seré decisions en un segon, el que és que només ens importa sobre la tendència de les coses com els conjunts de dades es fan més grans. Així que si el conjunt de dades és petit, hi ha en realitat una diferència bastant gran en aquests algoritmes. El tercer algoritme allà pren 13 vegades més, 13 vegades la quantitat de recursos per funcionar en relació amb la primera. 

Si el nostre conjunt de dades és de grandària 10, que és més gran, però no necessàriament enorme, podem veure que hi ha en realitat una mica de diferència. El tercer algoritme es torna més eficient. Es tracta en realitat del 40% - o 60% més eficient. Es triga 40% la quantitat de temps. Pot run-- pot prendre 400 unitats de recursos per processar un conjunt de dades de mida 10. Mentre que la primera algoritme, per contra, té 1.000 unitats de recursos per processar un conjunt de dades de mida 10. Però mira el que passa com els nostres números es posen encara més gran. 

Ara, la diferència entre aquests algoritmes començar a ser una mica menys aparent. I el fet que hi ha d'ordre inferior terms-- o més aviat, termes amb menor exponents-- començar a ser irrellevant. Si un conjunt de dades és de grandària 1000 i el primer algoritme corre en uns mil milions de passos. I el segon algoritme s'executa en mil milions i va un milió de passos. I la tercera algoritme s'executa en poc menys de mil milions de passos. És més o almenys mil milions d'passos. Aquests termes d'ordre inferior comencen per arribar a ser realment irrellevant. I només per realment martell casa el point-- si l'entrada de dades és de grandària a milions-- aquests tres o menys prendre'n un quintillion-- si meus matemàtiques és passos correct-- per processar una entrada de dades de la mida d'un milió. Això és un munt de passos. I el fet que un d'ells podria prendre un parell de 100.000, o una parella 100 milions menys encara quan estem parlant d'un nombre que big-- és una cosa irrellevant. Tots ells tendeixen a prendre aproximadament n en cubs, i així podríem realment referir a tots aquests algoritmes com estant en l'ordre de n en cubs o gran-O de n cubs. 

Aquí està una llista d'alguns dels més classes comunes complexitat computacional que anem trobem en algoritmes, en general. I també específicament en CS50. Aquests estan ordenats de generalment més ràpida a la part superior, a generalment més lent en la part inferior. Així algoritmes de temps constant tendeixen ser el més ràpid, sense tenir en compte de la mida de la entrada de dades es passa a. Ells sempre tenen una sola operació o una unitat de recursos per fer front a. Podria ser 2, podria ser de 3, podria ser 4. Però és un nombre constant. No varia. 

Algorismes temps logarítmiques són lleugerament millor. I un bon exemple de un algoritme de temps logarítmica segurament has vist per ara és el estripant de la guia telefònica trobar Mike Smith a la guia telefònica. Tallem el problema a la meitat. I així, a mesura que n es fa més gran i més gran i larger-- de fet, cada vegada que el doble n, només es necessita un pas més. Així que això és molt millor que, per exemple, el temps lineal. Què és si es duplica n, que pren el doble del nombre de passos. Si Triple N, es necessita triplicar el nombre de passos. Un pas per unitat. 

Després les coses es posen una mica més-- poc menys gran d'allà. Tens temps rítmic lineal, de vegades anomenat registre de temps lineal o simplement n log n. I anem a un exemple d'un algoritme que carreres en n log n, el que és encara millor que quadràtica temps-- n al quadrat. O el temps polinomi, n de dos qualsevol nombre més gran que dos. O temps exponencial, el que és encara worse-- C per al n. Així que alguns nombre constant elevar fins el poder de la mida de l'entrada. Així que si hi ha 1,000-- si el l'entrada de dades és de mida 1000, prendria C al poder 1000. És molt pitjor que temps polinomial. 

Temps factorial és encara pitjor. I de fet, en realitat ho fan Hi algoritmes de temps infinit, com ara, els anomenats sort-- estúpida la treball consisteix en barrejar aleatòriament un conjunt i després comproveu ja sigui ordenades. I si no és així, a l'atzar barrejar la matriu de nou i comprovar per veure si es tracta de resoldre el problema. I com vostè probablement pot imagine-- es pot imaginar una situació on en el pitjor dels casos, que la voluntat En realitat mai començar amb la matriu. Aquest algoritme aniria per sempre. I pel que seria un algoritme de temps infinit. Esperem que no va a escriure qualsevol moment factorial o infinit algoritmes en CS50. 

Per tant, anem a fer una mica més aspecte concret en algun simple classes de complexitat computacional. Així que tenim un exemple-- o dos exemples aquí-- d'algoritmes de temps constants, que sempre prendre una sola operació en el pitjor dels casos. Així que la primera exemple-- tenim una funció anomenada 4 per a vostè, que pren una matriu de mida 1000. Però llavors, aparentment en realitat no mirar en it-- no li importa realment el que és dins d'ella, d'aquesta matriu. Sempre simplement torna quatre. Per tant, aquest algoritme, malgrat el fet que té 1.000 elements no fer res amb ells. Només torna quatre. És sempre un sol pas. 

De fet, afegir 2 nums-- que que hem vist abans com bé-- simplement processa dos enters. No és un sol pas. En realitat és un parell de passos. Vostè rep una, s'obté b, s'agreguen junts, i vostès, els resultats de sortida. Així que és 84 passos. Però sempre és constant, independentment de a o b. Has de aconseguir una, obtenir b, afegiu junts, el resultat de sortida. Així que això és un algoritme de temps constant. 

Heus aquí un exemple d'un algorithm-- temps lineal un algoritme que gets-- que pren un pas addicional, possiblement, com la seva entrada creix un 1. Així que, diguem que estem buscant el número 5 a l'interior d'una matriu. És possible que tingui una situació en la vostè ho pot trobar bastant d'hora. Però també podria tenir una situació on podria ser l'últim element de la matriu. En una matriu de mida 5, si estem buscant el número 5. Prendria 5 passos. I de fet, imagino que hi ha No maig arreu d'aquesta matriu. Encara en realitat hem de mirar cada element de la matriu amb la finalitat de determinar si 5 és allà. 

Així que en el pitjor dels casos, i és que l'element és l'última en la matriu o no existeix en absolut. Encara hem de mirar tots els n elements. I així, aquest algoritme s'executa en temps lineal. Pot confirmar que per extrapolar una mica en dir: si tinguéssim una matriu de 6 elements i que estàvem buscant per al número 5, pot ser que prengui 6 passos. Si tenim un conjunt de 7 elements i estem buscant el número 5. Pot ser que prengui 7 passos. A mesura que afegim un element més al nostre matriu, que es necessita un pas més. Això és un algoritme lineal en el pitjor dels casos. 

Parella preguntes ràpides per a vostè. Quina és la runtime-- el que és el pitjor dels casos-runtime d'aquest fragment de codi en particular? Així que tinc un bucle de 4 aquí que corre des j és igual a 0, tot el camí fins m. I el que estic veient aquí, és que el cos del bucle s'executa en temps constant. Així, utilitzant la terminologia que ja hem parlat sobre-- el seria el pitjor dels casos temps d'execució d'aquest algorisme? Tome un segon. La part interna del bucle corre en temps constant. I la part exterior de la bucle es va a executar m vegades. Quin és el pitjor dels casos el temps d'execució en aquesta llista? Sabia vostè endevina gran-O de m? Vostè tindria raó. 

Què hi ha d'una altra? Aquest cop tenim una bucle dins d'un bucle. Tenim un bucle exterior que va des de zero a p. I tenim un bucle intern que s'executa de zero a p, ia l'interior d'això, Declaro que el cos de la bucle s'executa en temps constant. Quin és el pitjor dels casos el temps d'execució d'aquest fragment de codi en particular? Bé, de nou, tenim una llaç extern que s'executa p vegades. I cada iteració temps-- d'aquest bucle, més bé. Tenim un bucle intern que també corre p vegades. I després dins d'això, hi ha el constant petit fragment temps-- allà. 

Així que si tenim un bucle exterior que corre p vegades dins dels quals és un bucle interior que corre p vegades-- el que és el pitjor dels casos-runtime d'aquest fragment de codi? Sabia vostè endevina gran-O de p al quadrat? 

Sóc Doug Lloyd. Això és CS50.