Tudo bem, então, a complexidade computacional. Basta um pouco de um aviso antes de mergulhar em muito far-- este provavelmente estará entre as coisas mais matemática-pesados falamos em CS50. Esperemos que isso não vai ser muito esmagadora e vamos tentar e guiá-lo através do processo, mas apenas um pouco de um aviso justo. Há um pouco de matemática envolvida aqui. Tudo bem, então, a fim de torná- uso de nossos recursos computacionais no real mundo-- é realmente importante compreender algoritmos e como eles processam dados. Se temos uma realmente algoritmo eficiente, nós pode minimizar a quantidade de recursos que temos disponíveis para lidar com ele. Se tivermos um algoritmo que vai levar um monte de trabalho para processar um realmente grande conjunto de dados, é vai exigir mais e mais recursos, que é dinheiro, RAM, todo esse tipo de coisa. 

Assim, ser capaz de analisar uma algoritmo usando este conjunto de ferramentas, basicamente, pede ao question-- como é que este algoritmo de escala como nós jogamos mais e mais dados a ele? Em CS50, a quantidade de dados que estamos trabalhando com é muito pequena. Geralmente, nossos programas estão indo para executar em um segundo ou less-- provavelmente muito menos particularmente desde o início. 

Mas pense sobre uma empresa que lida com centenas de milhões de clientes. E eles precisam para processar que os dados do cliente. À medida que o número de clientes que eles tem se torna maior e maior, que vai exigir mais e mais recursos. Quantas mais recursos? Bem, isso depende de como analisamos o algoritmo, usando as ferramentas nesta caixa de ferramentas. Quando falamos sobre a complexidade da um algorithm-- que às vezes você vai ouvi-lo referido como tempo complexidade ou espaço complexidade mas nós apenas estamos indo para chamar complexity-- nós estamos geralmente falando o pior cenário. Dada a pior absoluta de pilha dados que poderia estar jogando para ele, como é que isto vai algoritmo processar ou lidar com esses dados? Nós geralmente chamar o pior caso tempo de execução de um algoritmo big-O. Assim, um algoritmo pode ser dito executado em O de n ou o de n ao quadrado. E mais sobre o que aqueles dizer em um segundo. 

Às vezes, porém, nós nos importamos sobre o melhor cenário. Se os dados forem tudo o que queríamos que seja e foi absolutamente perfeito e nós estávamos enviando este perfeito conjunto de dados através do nosso algoritmo. Como ele iria lidar nessa situação? Nós às vezes se referem a isso como big-Omega, portanto, em contraste com o big-O, temos big-Omega. Big-Omega para o melhor cenário. Big-O para o pior cenário. Geralmente, quando falamos de a complexidade de um algoritmo, nós estamos falando sobre o pior cenário. Portanto, manter isso em mente. 

E nesta classe, vamos geral para deixar a análise rigorosa de lado. Há ciências e campos dedicada a este tipo de coisa. Quando falamos de raciocínio por meio de algoritmos, que nós vamos fazer peça por peça para muitos algoritmos falamos na classe. Nós realmente estamos falando apenas de raciocinando através dele com o senso comum, não com fórmulas, ou provas, ou qualquer coisa assim. Então não se preocupe, nós não será transformando-se em uma classe grande de matemática. 

Então eu disse: nós nos preocupamos com a complexidade porque ele faz a pergunta, como que nossos algoritmos lidar com maior e maiores conjuntos de dados que está sendo jogado neles. Bem, o que é um conjunto de dados? O que eu quero dizer quando eu disse isso? Isso significa que tudo o que faz mais sentido no contexto, para ser honesto. Se tivermos um algoritmo, o Processos Strings-- estamos provavelmente falando sobre o tamanho da cadeia. Isso é os dados set-- o tamanho, o número de personagens que compõem a cadeia. Se estamos falando de um algoritmo que processa arquivos, poderíamos estar falando sobre como muitos kilobytes compreendem esse arquivo. E esse é o conjunto de dados. Se estamos falando de um algoritmo que lida com matrizes de uma forma mais geral, tais como algoritmos de classificação ou pesquisar algoritmos, nós provavelmente estamos falando sobre o número de elementos que compreendem uma matriz. 

Agora, podemos medir um algorithm-- em particular, quando eu digo que pudermos medir um algoritmo, I significa que podemos medir o quão muitos recursos que ele ocupa. Se esses recursos são, quantos bytes de RAM-- ou megabytes de memória RAM ele usa. Ou quanto tempo leva para executar. E nós podemos chamar isso de medir, de forma arbitrária, de f n. Onde n é o número de elementos do conjunto de dados. E f de n é o número de qualquer coisa. Quantas unidades de recursos faz que exigem a processar esses dados. 

Agora, nós realmente não me importo sobre o que f de n é exatamente. Na verdade, nós muito raramente will-- certamente nunca vai neste I class-- mergulhar em qualquer realmente profundo análise do que f de n é. Nós só vamos falar sobre o que f de n é aproximadamente ou o que tende a. E a tendência de um algoritmo é ditada pela sua mais alta expressão fim. E podemos ver o que eu entendemos por que, ao tomar uma olhada em um exemplo mais concreto. 

Então, vamos dizer que temos três algoritmos diferentes. O primeiro dos quais tem N cubos, algumas unidades de recursos para processar um conjunto de tamanho n dados. Temos um segundo algoritmo que leva n cubos mais recursos n ao quadrado para processar um conjunto de tamanho n dados. E nós temos uma terceira algoritmo que corre que em-- ocupa n cubos menos 8N quadrado n mais de 20 unidades de recursos para processar um algoritmo com o conjunto de tamanho n dados. 

Agora, novamente, nós realmente não estão indo para chegar a este nível de detalhe. Estou realmente só tem estes acima aqui como uma ilustração de um ponto que eu vou ser tornando num segundo, o que é que só realmente se importa sobre a tendência das coisas como os conjuntos de dados ficar maior. Portanto, se o conjunto de dados é pequeno, não há na verdade, uma diferença muito grande nestes algoritmos. O terceiro algoritmo lá leva 13 vezes mais tempo, 13 vezes a quantidade de recursos para rodar em relação à primeira. 

Se o nosso conjunto de dados é o tamanho 10, que é maior, mas não necessariamente grande, podemos ver que não há na verdade, um pouco de diferença. O terceiro algoritmo torna-se mais eficiente. Trata-se de, na verdade, 40% - ou 60% mais eficiente. Leva 40% a quantidade de tempo. Pode run-- pode demorar 400 unidades de recursos para processar um conjunto de tamanho 10 dados. Considerando que o primeiro algoritmo, por contraste, leva 1.000 unidades de recursos para processar um conjunto de tamanho 10 dados. Mas veja o que acontece como nossos números ficar ainda maior. 

Agora, a diferença entre estes algoritmos começam a se tornar um pouco menos aparente. E o facto de que existem de ordem inferior terms-- ou melhor, termos de menor exponents-- começam a se tornar irrelevante. Se um conjunto de dados é de tamanho 1000 e o primeiro algoritmo é executado em um bilhão de passos. E o segundo algoritmo roda em um bilhão e um milhão de passos. E o terceiro algoritmo roda em pouco menos de um bilhão de passos. É praticamente um bilhão de passos. Esses termos de ordem mais baixa começar para se tornar realmente irrelevante. E só para realmente martelo casa o ponto-- se a entrada de dados é de tamanho um milhões-- todos os três destes praticamente tomar um quintillion-- se minha matemática é passos correct-- para processar uma entrada de dados tamanho de um milhão. Isso é um monte de etapas. E o fato de que um deles poderia levar um par 100.000, ou um casal 100 milhões ainda menos quando estamos falando de um número big-- que é uma espécie de irrelevante. Todos eles tendem a tomar aproximadamente n cubado, e por isso seria verdade se referem para todos estes algoritmos como sendo da ordem de n cubos ou big-O de n em cubos. 

Aqui está uma lista de alguns dos mais classes de complexidade computacional comuns que vamos encontrar em algoritmos, geralmente. E também, especificamente, no CS50. Estes são ordenados a partir de geralmente mais rápido na parte superior, de forma geral, mais lento na parte inferior. Então, algoritmos de tempo constante tendem ser o mais rápido, independentemente do tamanho do entrada de dados que você passar em. Eles sempre têm uma operação ou uma unidade de recursos para lidar com eles. Pode ser 2, que poderia ser 3, pode ser 4. Mas é um número constante. Ele não varia. 

Algoritmos de tempo logarítmicas são ligeiramente melhores. E realmente um bom exemplo de um algoritmo de tempo logarítmica você certamente visto até agora é o dilacerando do livro de telefone para encontrar Mike Smith no livro de telefone. Nós cortar o problema pela metade. E assim como n fica maior e maior e larger-- na verdade, cada vez que você dobrar n, ele só tem mais um passo. Então, isso é muito melhor do que, digamos, o tempo linear. Que é se você dobrar n, ele leva o dobro do número de etapas. Se você triplicar n, é preciso triplicar o número de passos. Um passo por unidade. 

Em seguida, as coisas ficam um pouco more-- pouco menos grande de lá. Você tem tempo rítmica linear, por vezes, chamado registro de tempo linear ou apenas n log n. E nós vamos um exemplo de um algoritmo que é executado em n log n, que é ainda melhor do que quadrática tempo-- n ao quadrado. Ou tempo polinomial, n dois qualquer número maior do que dois. Ou tempo exponencial, o que é ainda worse-- C ao n. Assim, um número constante e elevada a a potência do tamanho da entrada. Portanto, se há 1,000-- se o entrada de dados é de tamanho 1.000, demoraria C ao poder 1000. É muito pior do que tempo polinomial. 

Tempo fatorial é ainda pior. E, de fato, não há realmente fazer existem algoritmos de tempo infinito, tais como, assim chamada sort-- burro cuja trabalho é para embaralhar aleatoriamente um array e, em seguida, verificar para ver se ele está classificado. E se não é, de forma aleatória embaralhar a matriz novamente e verificar para ver se ele está classificado. E como você provavelmente pode imagine-- você pode imaginar uma situação onde, no pior caso, que a vontade nunca realmente começar com a matriz. Algoritmo que iria correr para sempre. E para que seria um algoritmo de tempo infinito. Espero que você não vai ser escrito qualquer momento factorial ou infinito algoritmos em CS50. 

Então, vamos ter um pouco mais olhar em algum concreto simples classes de complexidade computacional. Portanto, temos um example-- ou dois exemplos aqui-- algoritmos de tempo constantes, que sempre tomar uma única operação no pior caso. Assim, o primeiro example-- nós temos uma função 4 chamado para você, que recebe um array de tamanho 1.000. Mas então, aparentemente, não realmente olhar a ele-- não se importa realmente o que é dentro dele, desse array. Sempre retorna apenas quatro. Então, esse algoritmo, apesar do facto de que ele leva 1.000 elementos não fazer nada com eles. Retorna apenas quatro. É sempre uma única etapa. 

Na verdade, adicionar 2 nums-- que que já vimos antes como bom-- apenas processa dois inteiros. Não é uma única etapa. É realmente um par etapas. Você ganha um, você começa b, você adicioná-los juntos, e você saída dos resultados. Então é 84 passos. Mas é sempre constante, independentemente de a ou b. Você tem que chegar a, b começar, adicione -los em conjunto, o resultado de saída. Então isso é um algoritmo de tempo constante. 

Aqui está um exemplo de um algorithm-- tempo linear que um algoritmo que leva gets-- um passo adicional, possivelmente, como sua entrada cresce 1. Então, vamos dizer que estamos procurando o número 5 para dentro de uma matriz. Você pode ter uma situação em que você pode encontrá-lo bastante cedo. Mas você também pode ter uma situação onde pode ser o último elemento da matriz. Em uma matriz de tamanho 5, se nós estamos olhando para o número 5. Levaria 5 passos. E, de fato, imaginar que há 5 não em qualquer lugar nessa matriz. Nós ainda realmente tem que olhar para cada elemento da matriz a fim de determinar 5 ou não existe. 

Assim, no pior caso, que é que o elemento é o último na matriz ou não existe de todo. Nós ainda temos de olhar para todos os n elementos. E assim este algoritmo executa em tempo linear. Você pode confirmar que, extrapolando um pouco, dizendo: se tivéssemos uma matriz de 6 elementos e estávamos procurando o número 5, isso pode levar 6 etapas. Se nós temos uma matriz de 7-elemento e nós estamos olhando para o número 5. Pode levar 7 passos. À medida que adicionamos mais um elemento para a nossa matriz, ele dá mais um passo. Isso é um algoritmo linear no pior caso. 

Casal perguntas rápidas para você. Qual é a runtime-- o que é o pior caso de tempo de execução deste trecho de código específico? Então, eu tenho um loop de 4 aqui que é executado de j é igual a 0, todo o caminho até m. E o que eu estou vendo aqui, é que o corpo do laço é executado em tempo constante. Então, usando a terminologia que nós já falamos o que about-- seria o pior caso tempo de execução deste algoritmo? Tome um segundo. A parte interna do lacete é executado em tempo constante. E a parte externa do loop está indo para executar m vezes. Então, qual é o pior caso de tempo de execução aqui? Será que você adivinha big-O de m? Você estaria certo. 

Como cerca de um outro? Desta vez temos um loop dentro de um loop. Nós temos um laço externo que vai de zero a p. E nós temos um loop interno que é executado de zero a P, e dentro de que, Afirmo que o corpo do loop é executado em tempo constante. Então, qual é o pior caso de tempo de execução deste trecho de código específico? Bem, mais uma vez, temos um loop externo que corre p vezes. E cada iteração tempo-- de malha que, em vez. Nós temos um laço interno que também executa p vezes. E, em seguida, dentro disso, há o constante pequeno trecho tempo-- lá. 

Então, se temos um circuito externo que p é executado vezes dentro dos quais é um loop interno que p é executado o que é vezes-- o pior caso de tempo de execução de esse trecho de código? Será que você adivinha big-O de p quadrado? 

Eu sou Doug Lloyd. Este é CS50.