Todo ben, entón, a complexidade computacional. Tan só un pouco de un aviso antes de mergullo moito far-- este probablemente estará entre as cousas máis matemática pesados falamos en CS50. Esperemos que isto non vai ser moi esmagadora e imos tratar e guía-lo a través do proceso, pero só un pouco de un aviso xusto. Hai un pouco de matemática aquí. Todo ben, entón, a fin de torná- uso dos nosos recursos computacionais no real mundo-- é realmente importante entender algoritmos e como procesan datos. Se temos unha realidade algoritmo eficiente, nós pode minimizar a cantidade de recursos que temos dispoñibles para tratar con el. Se temos un algoritmo que vai levar unha chea de traballo para procesar un realmente gran conxunto de datos, é vai esixir máis e máis recursos, que é diñeiro, RAM, todo este tipo de cousas. 

Así, ser capaz de analizar unha algoritmo usando este conxunto de ferramentas, basicamente, pide ao question-- como é que este algoritmo de escala como xogamos máis e máis datos a el? En CS50, a cantidade de datos que estamos traballando con é moi pequena. Xeralmente, os nosos programas van para realizar un segundo ou less-- probablemente moito menos particularmente desde o principio. 

Pero pense sobre unha empresa que trata con centos de millóns de clientes. E precisan para procesar que os datos do cliente. A medida que o número de clientes que ten se fai maior e máis grande, que vai esixir máis e máis recursos. Cantas máis recursos? Ben, iso depende de como analizamos o algoritmo, empregando as ferramentas nesta caixa de ferramentas. Cando falamos sobre a complexidade da un algorithm-- que ás veces vai ouvídelo chamada tempo complexidade ou espazo complexidade pero nós só estamos indo para chamar complexity-- estamos xeralmente falando o peor escenario. Dada a peor absoluta de pila datos que podería estar xogando para el, como é que isto vai algoritmo procesar ou tratar con estes datos? Nós xeralmente chamar o peor caso tempo de execución dun algoritmo big-O. Así, un algoritmo pode ser dito executado en O n ou o de n ao cadrado. E máis sobre o que aqueles dicir nun segundo. 

Ás veces, porén, nos importa sobre o mellor escenario. Se os datos son todo o que queriamos que sexa e foi absolutamente perfecto e que estaban enviando este perfecto conxunto de datos a través do noso algoritmo. Como ía tratar nesta situación? Nós ás veces se refiren a iso como big-Omega, polo tanto, en contraste co big-O, temos big-Omega. Big-Omega para o mellor escenario. Big-O para o peor escenario. Xeralmente, cando falamos de a complexidade dun algoritmo, estamos a falar sobre o peor escenario. Polo tanto, manter isto presente. 

E nesta clase, imos xeral para deixar a análise rigorosa de lado. Hai ciencias e campos dedicada a este tipo de cousas. Cando falamos de razoamento por medio de algoritmos, que nós imos facer peza por peza para moitos algoritmos falamos na clase. Nós realmente estamos falando só de raciocinando través del co sentido común, non con fórmulas, ou probas, ou algo así. Non te preocupes, non será transformando-se nunha clase grande de matemáticas. 

Entón eu dixen: nós nos preocupa coa complexidade porque fai a pregunta, como que os nosos algoritmos xestionar maior e maiores conxuntos de datos que está a ser xogado neles. Ben, o que é un conxunto de datos? O que quero dicir cando dixo iso? Isto significa que todo o que fai máis sentido no contexto, para ser honesto. Se temos un algoritmo, o Procesos Strings-- estamos probablemente falando sobre o tamaño da cadea. Iso é os datos set-- o tamaño, o número de personaxes que compoñen a cadea. Se estamos a falar dun algoritmo que procesa arquivos, poderiamos estar falando como moitos kilobytes comprenden o ficheiro. E ese é o conxunto de datos. Se estamos a falar dun algoritmo que trata sobre matrices de forma máis xeral, como algoritmos de clasificación ou buscar algoritmos, nós probablemente estamos falando do número de elementos que comprenden unha matriz. 

Agora, podemos medir un algorithm-- en particular, cando digo que pudermos medir un algoritmo, I significa que podemos medir o quão moitos recursos que ocupa. Se estes recursos son, cantos bytes de RAM-- ou megabytes de memoria RAM usa. Ou canto tempo leva para realizar. E podemos chamar iso de medir, de forma arbitraria, f n. Onde n é o número de elementos do conxunto de datos. E f n é o número de calquera cousa. Cantas unidades de recursos fai que esixen a procesar eses datos. 

Agora, nós realmente non me importa sobre o que f n é exactamente. En realidade, nós moi raramente will-- certamente non vai neste I class-- mergullo en calquera realmente profundo análise do que f n é. Nós só imos falar do que f de n é aproximadamente ou o que tende a. E a tendencia dun algoritmo é ditada pola súa máis alta expresión fin. E podemos ver que eu entendemos por que, ao tomar un ollo a un exemplo máis concreto. 

Entón, imos dicir que temos tres algoritmos diferentes. O primeiro dos cales ten N cubos, algunhas unidades de recursos para procesar un conxunto de tamaño n datos. Temos un segundo algoritmo que leva n cubos máis recursos n ao cadrado para procesar un conxunto de tamaño n datos. E nós temos unha terceira algoritmo que corre que em-- ocupa n cubos menos 8N cadrado n máis de 20 unidades de recursos para procesar un algoritmo co conxunto de tamaño n datos. 

Agora, de novo, nós realmente non están indo para chegar a este nivel de detalle. Estou realmente só ten estes arriba aquí como unha ilustración dun punto que eu vou ser facendo un segundo, o que é que só realmente importa sobre a tendencia das cousas como os conxuntos de datos queda maior. Polo tanto, se o conxunto de datos é pequeno, non hai de feito, unha diferenza moi grande nestes algoritmos. O terceiro algoritmo alí leva 13 veces máis tempo, 13 veces a cantidade de recursos para rodar en relación á primeira. 

O noso conxunto de datos é o tamaño 10, que é maior, pero non necesariamente grande, vemos que non hai en realidade, un pouco de diferenza. O terceiro algoritmo faise máis eficiente. Trátase de, en realidade, o 40% - ou 60% máis eficiente. Leva 40% a cantidade de tempo. Pode run-- pode levar 400 unidades de recursos para procesar un conxunto de tamaño 10 datos. Tendo en conta que o primeiro algoritmo, por contraste, leva 1.000 unidades de recursos para procesar un conxunto de tamaño 10 datos. Pero mira o que acontece como nosos números estar aínda maior. 

Agora, a diferenza entre estes algoritmos comezan a facer un pouco menos aparente. E o feito de que hai de orde inferior terms-- ou mellor, termos de menor exponents-- comezan a facer irrelevante. Un conxunto de datos é de tamaño 1000 eo primeiro algoritmo é executado en mil millóns de pasos. E o segundo algoritmo roda en mil millóns e un millón de pasos. E o terceiro algoritmo roda en pouco menos de mil millóns de pasos. É practicamente mil millóns de pasos. Estes termos de orde máis baixa comezar para facer realmente irrelevante. E só para realmente martelo casa o ponto-- a entrada de datos é de tamaño un milhões-- os tres destes practicamente tomar un quintillion-- se miña matemática é pasos correct-- para procesar unha entrada de datos tamaño dun millón. Iso é unha chea de pasos. E o feito de que un deles podería levar un par 100.000 ou unha parella 100 millóns aínda menos cando estamos a falar dun número big-- que é unha especie de irrelevante. Todos eles tenden a tomar aproximadamente n cubado, e por iso sería verdade se refiren para todos estes algoritmos como da orde de n cubos ou big-O n en cubos. 

Aquí está a lista de algúns dos máis clases de complexidade computacional comúns que imos atopar en algoritmos, xeralmente. E tamén, en concreto, no CS50. Estes son ordenados a partir de xeralmente máis rápido na parte superior, de forma xeral, máis lento na parte inferior. Entón, algoritmos de tempo constante tenden ser o máis rápido, independentemente do tamaño do entrada de datos que pasar. Eles sempre teñen unha operación ou unha unidade de recursos para tratar con eles. Pode ser 2, que podería ser 3, pódese 4. Pero é un número constante. El non varía. 

Algoritmos de tempo logarítmicas son lixeiramente mellores. E realmente un bo exemplo de un algoritmo de tempo logarítmica certamente visto ata agora é o dilacerando do libro de teléfono para atopar Mike Smith no libro de teléfono. Nós cortar o problema á metade. E así como n queda maior e máis grande e larger-- de feito, cada vez que dobrar n, el só ten un paso. Entón, iso é moito mellor que, digamos, o tempo lineal. Que é se dobrar n, el leva o dobre do número de etapas. Se triplicar n, hai que triplicar o número de pasos. Un paso por unidade. 

A continuación, as cousas están un pouco more-- pouco menos grande de alí. Ten tempo rítmica lineal, ás veces, chamado rexistro de tempo lineal ou só n log n. E nós imos un exemplo dun algoritmo que é executado en n log n, que é aínda mellor que cuadrática tempo-- n ao cadrado. Ou tempo polinomial, n dous calquera número maior que dous. Ou tempo exponencial, o que é aínda worse-- C ao n. Así, un número constante e elevada a a potencia do tamaño da entrada. Polo tanto, se hai 1,000-- o entrada de datos é de tamaño 1.000, tardaría C ao poder 1000. É moito peor que tempo polinomial. 

Tempo factorial é aínda peor. E, de feito, non hai realmente facer hai algoritmos de tempo infinito, tales como, así chamada sort-- burro cuxa traballo é para embaralhar aleatoriamente un array e, a continuación, comprobar a ver se está clasificado. E se non é, de forma aleatoria embaralhar a matriz de novo e comprobar a ver se está clasificado. E como probablemente pode imagine-- podes imaxinar unha situación onde, no peor caso, que as ganas nunca realmente comezar coa matriz. Algoritmo que ía correr para sempre. E para que sería un algoritmo de tempo infinito. Espero que non vai ser escrito calquera momento factorial ou infinito algoritmos en CS50. 

Entón, imos ter un pouco máis mirar nalgún concreto simple clases de complexidade computacional. Polo tanto, temos un example-- ou dous exemplos aqui-- algoritmos de tempo constantes, que sempre tomar unha única operación no peor caso. Así, o primeiro example-- temos unha función 4 chamado para ti, que recibe un array de tamaño 1.000. Pero entón, ao parecer, non realmente ollar a ele-- non lle importa realmente o que é dentro del, dese array. Sempre retorna só catro. Entón, ese algoritmo, a pesar do feito de que leva 1.000 elementos non facer nada con eles. Volve só catro. É sempre unha única etapa. 

De feito, engadir 2 nums-- que que xa vimos antes como bom-- só procesa dous enteiros. Non é unha única etapa. É realmente un par etapas. Gañou un, comeza b, vostede engadila los xuntos, e saída dos resultados. Entón é 84 pasos. Pero sempre constante, independentemente de a ou b. Ten que chegar a, b comezar, engade Los en conxunto, o resultado de saída. Entón iso é un algoritmo de tempo constante. 

Aquí está un exemplo dun algorithm-- tempo lineal que un algoritmo que leva gets-- un paso adicional, posiblemente, como a súa entrada crece 1. Entón, imos dicir que estamos a buscar o número 5 para dentro dunha matriz. Pode que unha situación na que pode atopalo moi cedo. Pero tamén pode ter unha situación onde pode ser o último elemento da matriz. Nunha matriz de tamaño 5, se nós estamos mirando para o número 5. Levaría 5 pasos. E, de feito, imaxinar que hai 5 non en calquera lugar nesa matriz. Aínda realmente ten que ollar para cada elemento da matriz a fin de determinar 5 ou non existe. 

Así, no peor caso, que é o que o elemento é o último na matriz ou non existe en absoluto. Aínda temos que mirar para todo n elementos. E así este algoritmo executa en tempo lineal. Pode confirmar que, extrapolando algo, dicindo: se tivésemos unha matriz de 6 elementos e estabamos a buscar o número 5, isto pode levar 6 etapas. Se temos unha matriz de 7-elemento e nós estamos mirando para o número 5. Pode levar 7 pasos. A medida que engadimos un elemento para a nosa matriz, dá un paso máis. Isto é un algoritmo lineal no peor caso. 

Parella preguntas rápidas para ti. Cal é a runtime-- o que é o peor caso de tempo de execución deste fragmento de código específico? Entón, eu teño un loop de 4 aquí que se executa de j é igual a 0, todo o camiño ata m. E o que eu estou a ver aquí, é que o corpo do lazo execútase en tempo constante. Entón, usando a terminoloxía que xa falamos o que about-- sería o peor caso tempo de execución deste algoritmo? Tomé un segundo. A parte interna do lacete execútase en tempo constante. E a parte exterior do loop está indo para realizar m veces. Entón, cal é o peor caso de tempo de execución aquí? Será que adiviña big-O m? Estaría ben. 

Como case outro? Esta vez temos un loop dentro dun loop. Temos un lazo externo que vai de cero a p. E nós temos un loop interno que se executa de cero a P, e dentro de que, Afirmo que o corpo do loop execútase en tempo constante. Entón, cal é o peor caso de tempo de execución deste fragmento de código específico? Ben, unha vez máis, temos un loop externo que corre p veces. E cada iteración tempo-- de punto que, en vez. Temos un lazo interno que tamén executa p veces. E, a continuación, dentro diso, hai o constante pequeno fragmento tempo-- alí. 

Entón, se temos un circuíto externo que p corre veces dentro dos cales é un loop interno que p execútase o que é vezes-- o peor caso de tempo de execución de este fragmento de código? Será que adiviña big-O p cadrado? 

Eu son Doug Lloyd. Este é CS50.