Algoritmos e estruturas de dados no Swift 5 - tenham sucesso na sua entrevista de trabalho para desenvolvedores de software! | Karoly Nyisztor | Skillshare

Velocidade de reprodução


  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x

Algoritmos e estruturas de dados no Swift 5 - tenham sucesso na sua entrevista de trabalho para desenvolvedores de software!

teacher avatar Karoly Nyisztor, Senior Software Engineer, Instructor

Assista a este curso e milhares de outros

Tenha acesso ilimitado a todos os cursos
Oferecidos por líderes do setor e profissionais do mercado
Os temas incluem ilustração, design, fotografia e muito mais

Assista a este curso e milhares de outros

Tenha acesso ilimitado a todos os cursos
Oferecidos por líderes do setor e profissionais do mercado
Os temas incluem ilustração, design, fotografia e muito mais

Aulas neste curso

49 aulas (2 h 2 min)
    • 1. Algoritmos e estruturas de dados no Swift 5

      2:46
    • 2. Seção 1: visão geral

      2:40
    • 3. Esse curso é para você?

      1:05
    • 4. Por que você deve aprender algoritmos

      1:14
    • 5. Pré-requisitos

      1:02
    • 6. Seção 2: notação grande do grande o

      2:31
    • 7. Tempo constante - O(1)

      5:40
    • 8. Tempo linear - O(n)

      4:17
    • 9. Tempo quadrático - O(n2)

      3:53
    • 10. Dicas para complexidade de polinômio O(n^k)

      1:32
    • 11. Tempo logarítmico - O(log n)

      1:56
    • 12. Resumo de grande O

      1:30
    • 13. Seção 3: recursão

      0:40
    • 14. O que é retorno?

      2:38
    • 15. Como funciona a recursão?

      4:45
    • 16. Pitfalls de recisão

      2:37
    • 17. Como evitar Recursion? infinita?

      1:51
    • 18. Seção 4: O poder dos algoritmos

      1:28
    • 19. Calcular soma (N)

      3:04
    • 20. Desafio de correspondência de pares

      4:17
    • 21. Encontre o índice de equilíbrio

      3:51
    • 22. O poder dos algoritmos - resumo

      1:49
    • 23. Seção 5: genéricos

      0:55
    • 24. Por que genéricas?

      1:24
    • 25. Tipos genéricos

      1:56
    • 26. Funções genéricas

      3:47
    • 27. Seção 6: tipos de coleta rápida

      0:55
    • 28. A matriz

      2:08
    • 29. Acessando a matriz

      1:09
    • 30. Modificando a matriz

      2:43
    • 31. O conjunto

      2:27
    • 32. Acessando e modificando o conjunto

      1:48
    • 33. Definir operações

      1:10
    • 34. O Protocolo de Hashable

      4:40
    • 35. O dicionário

      2:33
    • 36. Acessando e modificando o dicionário

      1:35
    • 37. Seção 7: classificação básica

      2:12
    • 38. Classificação de seleção

      5:33
    • 39. Classificação de seleção - resumo

      0:49
    • 40. Classificação de inserção

      7:58
    • 41. Ordenar inserção - resumo

      1:03
    • 42. Classificação de bolha

      5:05
    • 43. Classificação de bolha - resumo

      1:01
    • 44. Seção 8: classificação avançada

      0:51
    • 45. Classificar mesclar

      3:46
    • 46. Classificação de mesclagem - resumo

      0:55
    • 47. Classificação rápida

      3:28
    • 48. Quicksort - Resumo

      0:57
    • 49. Seção 9: pensamentos finais e recursos úteis

      2:30
  • --
  • Nível iniciante
  • Nível intermediário
  • Nível avançado
  • Todos os níveis

Gerado pela comunidade

O nível é determinado pela opinião da maioria dos estudantes que avaliaram este curso. Mostramos a recomendação do professor até que sejam coletadas as respostas de pelo menos 5 estudantes.

294

Estudantes

--

Sobre este curso

Dê uma olhada mais de perto em algoritmos e estruturas de dados e aprenda a trabalhar com eles para abordar de forma mais eficiente o desenvolvimento de software com o Swift. "Introdução a algoritmos e estruturas de dados no Swift 5" é um guia direto para resolver problemas de codificação de forma mais eficiente.

Neste curso abrangente, o autor Károly Nyisztor ajuda a se familiarizar com técnicas de pensamento algorítmico e otimização de código. Ele explica cada conceito usando exemplos fáceis de entender. Ele se concentra na aplicação prática, usando exemplos de código Swift hands-on que você pode usar para referência e prática.

Embora as demonstrações sejam implementadas no Swift, as lições podem ser aplicadas a qualquer linguagem de programação.

Durante todo o curso, o Károly caminha você por vários aplicativos de demonstração para demonstrar o poder dos algoritmos e a importância de escolher a solução certa.

Os tópicos incluem:

  • Pensamento algorítmico

  • A notação de grande O

  • Complexidade de tempo constante, linear, polinômio e logarítmico

  • Compreender a recursão e evitar armadilhas

  • Estudos de casos para encontrar soluções mais rápidas

  • Genéricos

  • Tipos de coleção Swift incorporados

  • Quando usar um conjunto, uma matriz ou um dicionário?

  • Implementando o tipo de seleção, o tipo de inserção e o tipo de bolha

  • Classificação avançada: classificação rápida e tipo de mesclagem

O estudo de algoritmos e estruturas de dados é fundamental para qualquer programador que planeja desenvolver sistemas de software que sejam escaláveis e performantes.
"Introdução a algoritmos e estruturas de dados no Swift 5" é o curso perfeito para você se você estiver interessado em trazer suas habilidades de codificação Swift para o próximo nível.

-------------

Para implementar os exercícios neste livro, você precisará de um Mac com o macOS 10.14.3 ou posterior. Você também vai precisar de Xcode 10.2.1 ou mais recente. Você pode baixar Xcode gratuitamente na Mac App Store.

Vamos usar o Swift 5 para implementar o código-fonte neste curso.

Todas as amostras são compatíveis com a versão mais recente do Swift. Vou atualizar o código-fonte conforme as alterações no idioma que o tornam necessário.

Os projetos estão disponíveis no Github, e você pode baixá-los do seguinte repositório: https://github.com/nyisztor/swift-algorithms. rápidos.

Conheça seu professor

Teacher Profile Image

Karoly Nyisztor

Senior Software Engineer, Instructor

Professor

My passion is helping people through online courses. So far, I've inspired over 50,000 students worldwide.

Hi there, my name is Károly Nyisztor. I'm a software engineer, online instructor, and book author. You can find my courses and books on all major platforms including Udemy, LinkedIn Learning, Lynda and Pluralsight.

I've worked with companies such as Apple, Siemens, SAP, Zen Studios, and many more. 
I've designed and built several enterprise frameworks, and I hold twelve patents related to inventions in the field of mobile computing.

I've developed over a dozen iOS apps and games- Libra Balance, My Travel Assistant, Travel Mate, iSyslog, GiftShopper, Zombie Run, to name a few.
Most of these apps have been featured by Apple(New a... Visualizar o perfil completo

Nota do curso

As expectativas foram atingidas?
    Superou!
  • 0%
  • Sim
  • 0%
  • Um pouco
  • 0%
  • Não
  • 0%
Arquivo de avaliações

Em outubro de 2018, atualizamos nosso sistema de avaliações para melhorar a forma como coletamos feedback. Abaixo estão as avaliações escritas antes dessa atualização.

Por que fazer parte da Skillshare?

Faça cursos premiados Skillshare Original

Cada curso possui cursos curtas e projetos práticos

Sua assinatura apoia os professores da Skillshare

Aprenda em qualquer lugar

Faça cursos em qualquer lugar com o aplicativo da Skillshare. Assista no avião, no metrô ou em qualquer lugar que funcione melhor para você, por streaming ou download.

Transcrições

1. Algoritmos e estruturas de dados no Swift 5: Algoritmos são essencialmente em ciência da computação. Eles estão literalmente em todos os lugares, mesmo que você ainda não tenha notado. Quando você planeja sua viagem, o GPS usa algoritmos de busca de rotas. E quando você assiste a um vídeo 4K no YouTube, ele é reproduzido perfeitamente graças aos algoritmos de compressão de áudio e vídeo. Que tal as incríveis cenas de jogos 3D? Eles não seriam possíveis sem algoritmos sofisticados de renderização. Você é um desenvolvedor de software? E se você pudesse escrever um código melhor e mais rápido? Talvez você esteja considerando uma carreira no desenvolvimento de software. Não seria ótimo passar na entrevista de emprego com cores voadoras. Oi, sou Carter. Quando você armazena, eu sou engenheiro de software, autor do MOOC e instrutor. Estou feliz em recebê-lo ao meu curso, Introdução a algoritmos e estruturas de dados em Swift cinco. Neste curso, eu ensino-vos a descobrir a complexidade do tempo de uma função. Você vai entender como os contêineres internos funcionam e você será capaz de explicar com confiança por que Quicksort é melhor do que a classificação bolha. Se você conhece algoritmos e estruturas de dados, você pode escrever código melhor. Seus programas serão executados mais rapidamente aplicando o algoritmo correto. Vou demonstrar tudo através da vida. codificação Swift executará testes de desempenho para comparar os tempos de execução de diferentes soluções com o mesmo problema. Você vai aprender sobre a notação Big O. Isso irá ajudá-lo a descobrir a complexidade das funções e algoritmos. Então vou mostrar-vos o poder dos genéricos. Estande genérico no núcleo da biblioteca padrão rápida, verá genéricos em ação e você se familiarizará rapidamente com eles. Em seguida, falaremos sobre os tipos de coleção embutidos do Swift. Eu mostro-lhe como implementar algumas das estruturas de dados fundamentais usando o Swift. Então vamos mergulhar nos algoritmos de classificação do básico ao avançado. Vou explicar e implementar a classificação de seleção, classificação de inserção, classificação de bolha, classificação mesclagem e o famoso algoritmo QuickSort. Eu uso técnicas de visualização ao longo do curso. E eu divido conceitos complexos em pedaços simples e fáceis de entender. No final deste curso, você saberá como implementar programas mais rápidos e melhores. Você também entenderá como funcionam as estruturas de dados mais populares e os algoritmos de classificação. Você aprende a implementar código mais eficiente junto com as melhores práticas de programação Swift que você pode aplicar instantaneamente em seus aplicativos. Discursos ao longo do tempo investimento. Vejo você na primeira lição. 2. Seção 1: visão geral: Oi, eu sou carga na loja e bem-vindo à Introdução a algoritmos e estruturas de dados em Swift. Criei este curso para ajudá-lo a escrever código melhor e mais eficiente, você aprenderá sobre alguns dos algoritmos e estruturas de dados comumente usados. Começamos aprendendo sobre como analisar a eficiência dos algoritmos. Primeiro, vamos falar sobre a grande notação O, que é um modelo matemático para medir e classificar algoritmos. Ele estimou a eficiência de tempo de execução de um algoritmo como uma função do tamanho de entrada. Vamos falar sobre tempo constante, tempo linear, tempo polinomial e tempo logarítmico. Para entender esses conceitos, vamos implementar, analisar e comparar vários algoritmos. Então falamos sobre recursão e como evitar o problema da recursão infinita. Muitos algoritmos e estruturas de dados dependem da recursão. Assim, é imperativo compreender como funciona a recursão. Passamos para mostrar os benefícios práticos do uso de algoritmos. Vamos comparar amostras não otimizadas com aquelas que dependem de algoritmos. Se você teve alguma dúvida sobre a importância dos algoritmos, esses exemplos vão convencê-lo. Em seguida, mergulhamos em genéricos. Você deve entender genéricos antes de começarmos a estudar estruturas de dados e algoritmos. Então falamos sobre as estruturas de dados incorporadas. Você aprenderá sobre o array, o conjunto e o dicionário antes de passar para os algoritmos de classificação. Em seguida, estudamos e implementamos a classificação de seleção, classificação de inserção e classificação de bolha. Vamos analisar a eficiência de cada um desses algoritmos de classificação e os representamos visualmente. Continuaremos com mais dois algoritmos avançados de classificação. Implementamos a classificação de mesclagem e o QuickSort no Swift. Finalmente, vou compartilhar alguns recursos on-line úteis que ajudarão você a aprimorar suas habilidades de codificação e resolução de problemas. Depois de terminar este curso, conhecerá todos os conceitos fundamentais relacionados com algoritmos e estruturas de dados. Você terá uma boa compreensão de conceitos como recursão e genéricos. Você verá como os algoritmos de classificação populares funcionam e a maneira como eles podem ser implementados usando o Swift como a primeira parte de uma série sobre programação Swift. Este curso é um passo essencial para aprofundar os algoritmos, estruturas de dados e programação em geral. 3. Esse curso é para você?: Agora vamos ver se este é o caminho certo para você. Embora eu expliquei quase todas as linhas de código que escrevo neste curso, você deve saber os conceitos básicos de programação. Coisas como métodos, loops ou condições devem ser familiares para você. Não é um problema se você é relativamente novo na programação. Não se preocupe. Se você ainda não ouviu falar sobre a grande notação O, recursão ou genéricos. Vou explicar cada conceito desde o início. Você é novo no Swift? Não é um problema. Você já trabalhou com qualquer outra linguagem de programação como Java, C-sharp, ou até mesmo aviões C. Nesse caso, você será capaz de acompanhar comigo. Você pode achar este curso útil mesmo se você estiver usando uma linguagem de programação diferente. Obter insights sobre o Swift e aprender como otimizar seu código irá elevar sua carreira e habilidades profissionais. Agora, isso descreve você se sim, esta é a pontuação perfeita para aprender sobre estruturas de dados e algoritmos em Swift. 4. Por que você deve aprender algoritmos: Então, por que você deveria estudar algoritmos em primeiro lugar? Uma vez que passamos os aplicativos básicos do hello world iniciante, começamos a perceber que a implementação de sistemas de software complexos requer uma abordagem diferente. O software que costumava funcionar bem durante nossos testes, torna-se incrivelmente lento e frequentemente falha na produção. Aprendemos da maneira mais difícil que não preparamos nosso sistema para uso na vida real. Enquanto ele correu sem problemas com os dados de teste, ele falha miseravelmente quando a realidade chuta n. algoritmos de computador foram desenvolvidos e refinados ao longo do último par de décadas. O estudo de algoritmos e estruturas de dados é fundamental para qualquer programador que planeja desenvolver sistemas de software escaláveis e de desempenho. Algoritmos são indispensáveis para a construção de software capaz de gerenciar grandes quantidades de dados ou resolver problemas complexos. E as estruturas de dados nos permitem acessar e armazenar os dados de forma eficiente. Não podemos evitar estruturas de dados enquanto estudamos algoritmos. Além disso, você vai encontrar questões relacionadas com algoritmos e estrutura de dados durante entrevistas de emprego. 5. Pré-requisitos: Agora, antes de começarmos a investigar algoritmos e estruturas de dados, vamos dar uma olhada rápida no que você deveria saber. Este curso é amigável para iniciantes. Alguma experiência de programação básica é necessária, mas você não precisa ter realmente trabalhado com o próprio Swift. Para implementar os exercícios neste curso, você precisará de um Mac com macOS Catalina ou Big Sur e Xcode 12 ou mais recente. Você pode baixar Xcode gratuitamente na Mac App Store. Vamos usar 55 para implementar o código-fonte neste curso. São as amostras são compatíveis com a última versão Swift. Vou atualizar o código-fonte à medida que as alterações no idioma o tornam necessário. Os projetos estão disponíveis no GitHub e você pode baixá-los a partir do seguinte repositório. O idioma Swift está disponível como código aberto. Visite o Swift.org para ver tudo o que está relacionado. E sem isso dito, vamos mergulhar. 6. Seção 2: notação grande do grande o: Bem-vindo à segunda seção deste curso sobre algoritmos em Swift. Nesta seção, vamos falar sobre complexidade computacional. A notação beagle é um modelo matemático usando ciência da computação para descrever a eficiência de algoritmos como uma função de seu tamanho de entrada. A melhor maneira de entender o Big O completamente é através de exemplos de código. Portanto, ilustramos cada conceito usando codificação rápida aqui como as ordens comuns de crescimento ou complexidades sobre as quais vamos falar. Nesta seção, Tempo Constante descreve um algoritmo que sempre é executado na mesma quantidade de tempo, independentemente do tamanho de entrada. Tempo Linear descreve um algoritmo cujo desempenho cresce linearmente e em proporção direta ao tamanho do conjunto de dados de importação. Tempo quadrático representa em algoritmo cujo desempenho é diretamente proporcional ao quadrado do tamanho do conjunto de dados de entrada. Esse comportamento é típico com algoritmos que envolveram iterações aninhadas sobre o conjunto de dados . Iterações aninhadas mais profundas resultam em tempo cúbico, tempo aquático e pior tempo logarítmico tempo tempo logarítmico representa ah, algoritmo altamente eficiente. Por exemplo, a técnica de busca binária popular executa em tempo logarítmico saber que só cobrimos os conceitos básicos de grande Oh, esse conhecimento é suficiente para entender a eficiência dos algoritmos de classificação apresentados nas pontuações. Esta visualização gráfica é o tempo de execução de alguns dos algoritmos de classificação mais populares. À medida que o tamanho de entrada aumenta, as diferenças de desempenho tornam-se cada vez mais prevalentes quando o Condado de entrada pequenos todos os algoritmos executam quase igualmente. Na verdade, ao testar com pequenos conjuntos de dados, podemos até ter a impressão de que o algoritmo com a complexidade logarítmica tem os piores desempenhos. No entanto, como o tamanho dos dados diz cresce verá claramente as diferenças nos próximos vídeos. Vamos analisar as várias complexidades do algoritmo através da prática, acordo com exemplos. Começamos mostrando o tempo constante e terminaremos nesta seção com o tempo logarítmico . 7. Tempo constante - O(1): tempo constante descreve um algoritmo que requer a mesma quantidade de tempo para ser executado independentemente do tamanho de entrada. Aqui está o que obtemos Se visualizarmos o tempo de execução de um algoritmo que é executado em tempo constante, o tamanho da entrada não afeta o tempo de execução. Em outras palavras, o tempo de execução permanece constante no algoritmo, que tem um tempo constante. A complexidade é executada pelo mesmo período de tempo. Se ele opera em uma ou várias 1000 ou 1.000.000 entradas na demonstração a seguir foram embora. Implementar alguns exemplos que executar tempo constante Não, que vamos contar com playgrounds rápidos ao longo das pontuações irá implementar uma classe de utilidade para medir. Os artistas contarão com essa classe de utilidade para realizar medições na demonstração atual e em vários outros projetos futuros. Para ilustrar o tempo constante, complexidade irá criar uma função que foram formas Check Honoree. O segundo exemplo depende para mapa hash. Olhe para cima. Vamos medir os tempos necessários para recuperar valores com base em suas chaves de dicionários Steve de vários tamanhos. Se implementado corretamente, a pesquisa de mapa de hash deve acontecer em tempo constante. Tudo bem, agora, vamos mudar para Ex Corde se você quiser me acompanhar. Baixe o repositório de Get Hub abriu o maior playground do grande e velho SRC. Além disso, você pode encontrar o código-fonte para esta demonstração na página do playground em tempo constante. Primeiro, implementamos o utilitário de benchmarking. A classe de temporizador banco tem um único método chamado bloco de medida. O método de tipo de bloco de medida tem um argumento de fechamento. O código de medida é executado 10 vezes e armazenamos os tempos de execução individuais. Em Honore. Contamos com as estruturas de núcleo quarts. Veja uma função de tempo de mídia atual para recuperar o tempo absoluto atual. Ao contrário de qualquer propriedade ou CF. Tempo absoluto. Obter corrente. Veja o tempo atual da mídia é confiável, uma vez que não está sujeito a alterações na referência de tempo externa , a rocha medida é executada entre a criação da hora de início e hora de término. Armazenamos o tempo de execução na matriz de tempos de execução. Após 10 iterações, calculamos o tempo médio de execução, a causa reduzida ou uma função dos fechamentos eventualmente em todos os elementos da matriz que no nosso caso, resume todos os itens em teoria. Finalmente, dividimos o resultado pelo número de iterações, que nos dá o tempo médio de execução. Em seguida, implementamos uma função que leva uma matriz e verifica. Se o primeiro elemento é zero. A função simples é executada em tempo constante. Aí está a execução. tempo deve ser o mesmo, independentemente do tamanho do em cerâmica. Agora vamos provar que nossa teoria realmente invocar o início com função zero com três matrizes, a primeira taxa tem apenas três elementos. O 2º 1 tem 10.000 entradas e o terceiro array é enorme com um milhão de itens. Nosso benchmark mostra que o tamanho da taxa de entrada não afeta o tempo de execução. Existem apenas diferenças insignificantes na ordem dos microssegundos. Outro algoritmo, que é executado em tempo constante, é o mapa de hash. Olhe para cima. Contamos com o dedo do pé função auxiliar gerada. Grandes dicionários de tamanho personalizado geram tomadas picadas no argumento de importação chamado tamanho. Este argumento fornece o tamanho do dicionário gerado. A função retorna um dicionário com chaves do tipo string e valores do tipo inteiro. Para nós, criamos no dicionário vazio. Em seguida, eu valido o parâmetro de entrada de tamanho, usando a instrução guards. Se o tamanho não for maior que zero, retornamos o anti dicionário. Caso contrário, geramos as chaves e os valores. Eu uso um para em loop toe alfabetizado de zero até, mas não incluindo tamanho varia. Nós ou de zero para o tamanho menos um. A chave é a representação de cadeia de caracteres do índice. Então dissemos que o valor para a chave dada, que é o próprio índice. No final, obtemos um campo de dicionário com pares de valor de chave no inteiro de cadeia de forma. Agora vamos criar dicionários de diferentes tamanhos. O 1º 1 chamado Small Dictionary, contém apenas três pares de valor de chave. Dicked médio tem 500 pau enorme contém 100.000 chaves e valores. Contamos com o método de tempo de bancada ou bloco de medida para descobrir o tempo de execução do dicionário. Procure depois de executar a demonstração. Nós realmente vemos que o tempo que leva para encontrar um elemento não depende do tamanho do dicionário. Nosso teste mostra que a pesquisa de dicionário tem uma complexidade de tempo constante. As diferenças nos tempos de execução estão abaixo do microssegundo. Mundo fresco. Algoritmos de tempo constante são ideais porque não são afetados pelo tamanho da entrada. Infelizmente, nem sempre é possível encontrar uma solução que funcione em tempo constante. 8. Tempo linear - O(n): Nesta palestra, vamos falar sobre a complexidade do tempo linear. Tempo Linear descreve um algoritmo cujo desempenho cresce linearmente e em proporção direta ao tamanho do conjunto de dados de entrada. Este gráfico representa o tempo de execução de um algoritmo que é executado em tempo linear. Há uma correlação de 1 a 1 entre o tamanho da entrada e o tempo de execução. O algoritmo forno tempo de execução com complexidade de tempo linear aumenta na mesma taxa os dados de importação disse cresce. Por exemplo, se 1000 entradas levassem um segundo para processar que 10.000 exigiria 10 vezes mais, isso é 10 segundos. 100.000 entradas seriam processadas em 100 segundos e assim por diante. Como os dados de importação dizem cresce, o tempo de processamento de algoritmos aumenta para É por isso que é chamado de tempo linear. Em seguida, irá implementar alguns exemplos que executam em tempo linear. Primeiro, vou mostrar-vos uma função que resume os elementos de Honore. A próxima função que implementamos retorna o número de deveria e até mesmo inteiros de Honore, ambas as funções alfabetizadas através de todo o Ari. Portanto, o tempo de cálculo está diretamente relacionado ao tamanho da teoria. Temos complexidade linear em ambos os casos para medições de desempenho dependerá do temporizador da bancada . Seremos isso na lição anterior. Se quiser me acompanhar, baixe o repositório do Get Hub. Abra o grande e velho playground do grande O SRC Além disso, você pode encontrar o código-fonte para esta demonstração na página do playground de tempo linear, direi que a complexidade do tempo linear precisará de um aumento de tamanhos diferentes. Então, vamos forçado implementar de função, que gera tamanho personalizado os raios com conteúdo aleatório. A função gerar Render Marie leva dois argumentos tamanho, que dá o tamanho do dory gerado e valor máximo, que fornece o maior valor permitido para os elementos. Usamos os nossos uniformes para um umótimo conteúdo aleatório para a teoria. Em seguida, criamos uma função que resume os elementos da entrada. Tory. Esta função interessa através dos elementos do Imperatori. O alguns dos elementos são armazenados na variável chamada resultado. Finalmente, o funcional retorna a soma de todos os inteiros a partir thean cerâmica saber que poderíamos ter usado a redução ou uma função toe, calcular a soma. Mas implementar a solução personalizada torna evidente que reiteramos ao longo de todo o Ari , vamos testar a alguma função com três matrizes de tamanhos diferentes. O primeiro Ray tem 100 itens, o próximo tem 1000 e o último tem 10.000 elementos. Depois de executar nossos testes, os valores de medição de desempenho exibidos no conselho provam que o tempo de execução é linear, a função de soma analfabeta através de todos os elementos da matriz. Assim, é normal que o tempo de execução aumente proporcionalmente com o tamanho da matriz. Aqui está outra função que precisa iterado através de todos os elementos da lista de entrada . A contagem são mesmo função verifica cada item para descobrir se é ímpar ou par. Eu usei o operador do módulo para verificar se há um restante ao dividir o número por dois . O número é mesmo se o restante zero. Caso contrário, o número é ímpar. Nossos testes confirmaram que o mesmo é, de fato, uma função que corre em tempo linear. O tempo de execução aumenta na mesma taxa que os dados de entrada disse cresce. Encontramos algoritmos de tempo linear com bastante frequência. Mais dados geralmente significa mais tempo de processamento, reduzindo a complexidade de tempo de um algoritmo de tempo linear para tempo constante não é uma tarefa fácil e pode nem ser possível em todos os casos. Mas como você verá nas próximas palestras, há ainda piores complexidades do tempo. 9. Tempo quadrático - O(n2): poderia. Tempo de repouso representa um algoritmo cujo desempenho é diretamente proporcional ao quadrado do tamanho do conjunto de dados de entrada. Como você pode ver neste gráfico, o tempo de execução aumenta acentuadamente mais rápido do que os tamanhos de um put. O tempo de execução de um algoritmo com complexidade de tempo quadrático aumentará como um quadrado dos conjuntos de dados de importação tamanho quadrático cúbico e complexidades de tempo quadrático são resultado de operações aninhadas no conjunto de dados. Você deve tentar evitá-los sempre que possível devido ao impacto negativo no desempenho geral . Digamos que seu algoritmo de tempo quadrático processa 100 entradas em 100 milissegundos. Para 2000 entradas, o algoritmo seria executado por 40 segundos e 4000 entradas seriam processadas em um pouco mais de 26 minutos. O tempo de execução aumentou ainda mais acentuadamente com o tamanho da importação no caso da complexidade do tempo cúbico ou aquático . Na demonstração a seguir, vamos construir uma função que grandes tabelas de multiplicação. A função usará dois loops aninhados devido às iterações aninhadas. Este algoritmo tem uma complexidade de tempo quadrático. Se você quiser acompanhar comigo, baixe o repositório de levantar aberto o playground Big O da pasta Big O SRC. Você pode encontrar o código-fonte para esta demonstração na página do playground de tempo quadrático. Agora vamos chegar a dois x marcado. Primeiro, implementamos uma adição útil. Toe são utilitário de benchmarking. Tivemos uma propriedade de tempo formatado para o tipo de intervalo de tempo CF. Esta propriedade fornece uma representação de string concisa do valor do intervalo de tempo, que também inclui as unidades certas de tempo, que varia de nove segundos para segundo. Em seguida, irá implementar uma função para demonstrar a complexidade do tempo quadrático. A função My table leva um argumento inteiro, que dá o tamanho da matriz, que contém inteiros positivos no intervalo um para o tamanho. A função retorna os resultados da multiplicação de cada elemento em teoria com todos os outros valores. Usamos dois loops para calcular o resultado. O loop externo interessa através dos índices de teoria. O loop interno leva o valor encontrado no índice externo e o multiplica com cada item da mesma matriz. O L colocar é uma tabela de multiplicação. Vamos verificar o que obtemos para o valor de entrada. 10. Agora vamos analisar como os dois loops aninhados influenciam o tempo de processamento de dois elementares. O loop externo iterado duas vezes o loop interno analfabeta duas vezes para cada isolamento externo . Isso nos dá quatro iterações no total para um três elementary. A contagem total de libertação é três vezes três. Há nove para 10 elementos. A função parecerá 100 vezes. O número de iterações sobe é um quadrado do tamanho dos dados de entrada. Vamos executar alguns testes de desempenho para provar que nossa função tem uma complexidade de tempo quadrático . Chamamos a função comercializável com os raios de diferentes tamanhos, e amamos os tempos de execução. Então o Conselho, os números são convincentes. Podemos ver claramente os saltos quadráticos no tempo de execução. Agora eu gostaria de acrescentar que, especialmente para entradas menores, as medições podem nem sempre refletir a complexidade do tempo quadrático devido ao compilador sob o capô e otimização de hardware. 10. Dicas para complexidade de polinômio O(n^k): loops aninhados dentro do método ou função devem ser sempre um sinal de aviso, e você deve evitá-los a todo custo. Sempre que você encontrar dois ou mais loops que se assemelham a bonecas de aninhamento russas, pergunte a si mesmo se as iterações de mensagem são realmente necessárias para resolver esse problema específico . Primeiro, documente o código questionável usando Commons dedicado ou melhor ainda em um aviso se suportado pelo compilador fornecido. Em seguida, implementar testes unitários. Dedo. Eu, como o problema de desempenho causado pelos loops aninhados, finalmente tentei resolver o problema substituindo as durações necessárias por um algoritmo mais eficiente. complexidade do tempo polinomial é geralmente o resultado de codificação apressada produzida por desenvolvedores que gostam de tempo ou experiência, ou talvez ambos. Na maioria das vezes, você encontrará uma solução melhor na seção chamada O Poder dos Algoritmos verá exemplos de substituição de abordagens ineficientes por soluções que trazem enormes ganhos de desempenho . Às vezes, realmente não há melhor maneira de resolver um problema específico, e você pode se livrar dos loops aninhados em tais casos. Documente cuidadosamente as partes do tribunal afetadas e descreva por que ele funciona dessa maneira. Descreva também os problemas de desempenho que podem causar com conjuntos de dados maiores 11. Tempo logarítmico - O(log n): algoritmos avançados como a técnica de busca binária executar em tempo logarítmico. tempo logarítmico significa que o tempo de execução aumenta linearmente, enquanto o tamanho dos dados de entrada cresce exponencialmente. Por exemplo, se levar um milissegundo para calcular 10 elementos, levará a milissegundos para calcular 100 elementos três milissegundos para calcular 1000 elementos e assim por diante. Comprar uma classificação rápida pesquisa e dividindo tipo conquistado de algoritmos geralmente executado em tempo logarítmico. Primeiro, vamos dar uma olhada no polegar de luxo. Em matemática. O algoritmo é a operação inversa para explicar a ação NC. Os logaritmos de X a base B é o número real único. Por que tal B ao poder? Por que X, por exemplo, um luxo? Eles de 1000 base 10 é três como 10 para o poder três é 1000. A base para mais tempo eles de 16 é também, como quatro para o poder para é 16. A base de três logaritmos de 27 é três como três para o poder três é 27 e a base dois logaritmos de 1024 é 10. Quanto à potência, 10 é 1024. Em outras palavras, o algoritmo de um número é o dedo do pé expoente, que outro número fixo, a base, deve ser aumentado para produzir esse número em ciência da computação ao medir o desempenho de algoritmos, a base dos logaritmos não é especificada porque o resultado Onley muda por um fator constante quando usamos outra base. Portanto, um fator constante é geralmente desconsiderado na análise de algoritmos. 12. Resumo de grande O: com dedicado esta seção inteira dedo do pé a notação maior. Compreender a complexidade do tempo abre a ponta da estrada Trabalhando com algoritmos. Falamos sobre complexidade de tempo constante, onde o tempo de execução é constante e não depende do tamanho da importação. Verificar o primeiro elemento de uma matriz ou recuperar um item de um dicionário são bons exemplos para a complexidade do tempo constante. complexidade de tempo linear descreve um algoritmo cujo tempo de execução cresce em proporção direta ao tamanho da entrada. Por exemplo, enumerando através dos elementos de trabalhos honorários em tempo linear, os tempos de execução de algoritmos de tempo quadrático subir como um quadrado dos dados de importação, o referido tamanho complexidade de tempo quadrático é produzido por um loop aninhado em outro loop, como vimos em nossa tabela de multiplicação. Exemplo. Tente evitar a complexidade do tempo polinomial como quadrático, aquático ou cúbico, pois pode se tornar um enorme gargalo de desempenho. Tempo logarítmico descreve algoritmos complexos como a classificação rápida e mostra seus benefícios ao trabalhar com conjuntos de dados maiores no. As próximas seções com fora para o mundo dos algoritmos exportarão a diferença entre a abordagem ingênua da força bruta e a que implementamos com eficiência em mente. 13. Seção 3: recursão: na programação. A repetição pode ser descrita usando loops como o Four Loop ou o While Loop. Outra maneira é usar Riker Shin. Encontramos Rikers com pouca frequência. Por quê? Estudar algoritmos e estruturas de dados. Assim, é importante entender o que é Rickerson. Vou mostrar-vos como a incursão funciona através de exemplos de codificação de vida. Rickerson é uma técnica útil, mas não vem sem armadilhas. Eu acho que é esta seção mostrando como evitar problemas comuns ao usar Rikers em seus quinto projetos. 14. O que é retorno?: Vamos esclarecer qual é a versão Ryker. Por definição, recordação é uma forma de resolver um problema que está ocorrendo. Meu repetidamente resolver problemas sub similares na programação podemos ter funções recursivas. A função é recursiva. Se isso causar-se, o carro pode acontecer diretamente, como neste caso ou indiretamente. Se a função causar outra função, que por sua vez invoca bem a primeira função, muitas vezes encontrar estruturas de dados recursivos para uma estrutura de dados é recursiva se você pode descrevê-lo em termos de si mesmo. Por exemplo, uma lista vinculada pode ser descrita como um nó de lista, seguido por uma lista vinculada. Certo, vamos implementar uma estrutura de dados recursiva. Então aqui está um simples copo de notas. Cada nota pode vincular com o próximo nó através da próxima propriedade. A nota também que tem um valor de cadeia de caracteres de tipo. Finalmente, eu forneço um Isar inicial, que define o valor Propriedade. Agora que não temos nenhum tipo, vamos ser uma lista vinculada. Primeiro, crio cada nota e atribuo um valor que corresponda ao seu nome. Então eu disse que a próxima propriedade de cada nota para formar uma lista de links. A próxima nota para o nó um é não para não para a próxima nota será Não. Três. E finalmente eu termino a lista vinculada definindo a próxima nota para a nota três para se ajoelhar. Agora vamos implementar a função que inverte a lista vinculada e príncipe o valor em cada nó. Vou chamar os nós de análise de função, o pessoal. Sua função tem um parâmetro de tipo nó. Se a entrada Não, este Neil eu sair da função. Caso contrário, eu imprimir o valor do nó dado. Em seguida, eu chamei o pessoal sua função recursiva Lee passando no próximo nó. Finalmente, chamo a função de notas de barras com a primeira nota como parâmetro de entrada, o cônsul mostra os valores esperados. Uma vez que a estrutura de dados é recursiva, eu era capaz de usar a canela Riker iterado através dele, usando uma função recursiva. Os registros em não necessariamente produzirão código mais rápido ou mais eficiente, mas geralmente fornece uma alternativa elegante para qualquer um deles. Dave se aproxima e requer menos linhas de código 15. Como funciona a recursão?: Até agora, vimos alguns exemplos de funções recursivas e estruturas de dados. Agora vamos ver como Rikers está funcionando. Vou calcular o fatorial de um inteiro positivo. E este é um problema que pode ser resolvido usando Ryker Shin, vez que o fatorial é definido como o produto fora dos inteiros de um para o fim. Então aqui está uma função fatorial rápida que calcula o fatorial de um inteiro positivo. A função assume inteiro sem sinal como argumento. Se o parâmetro de entrada for menor do que para a função retorna um. Caso contrário, a função retorna o produto fora da entrada e o resultado de chamar a função com um argumento que é menor por um. Os custos recursivos continuam até que a função é chamada com um valor que é menor do que dois. Para entender como os registros em funciona, aqui está uma representação gráfica do que está acontecendo ao calcular fatorial de três. Sempre que uma chamada aninhada acontece, a execução fora da chamada anterior é suspensa e seu status é armazenado. O instantâneo de seu contexto, isto é, é bons parâmetros de entrada e variáveis locais é persistida. Toda essa informação é armazenada em uma estrutura conhecida como estaca cáustica ou execução. O cáustico é uma estrutura de pilha que mantém naufrágio fora do ponto onde o controle deve ser retornado após uma sub-rotina termina sua execução. Quando a chamada aninhada é concluída a execução, seu contexto é destruído e o controle é retornado para o colarinho. Eventualmente, voltamos para a primeira chamada de função. Todos os contextos aninhados são destruídos até então, e o resultado final é retornado ao colarinho. Agora vamos mudar para Ex Corde. Eu fui em frente e classifiquei um projeto de playground. Vamos começar por implementar uma função que cock é o fatorial de um inteiro positivo, e a função leva um inteiro sem sinal de 64 bits como argumento, e também retorna este tipo. Este problema pode ser resolvido usando verificações de recordação. O fatorial é definido como o produto fora dos inter jurados de uma extremidade do dedo do pé, o fatorial off um e zero é um, então nós transformamos um para entrada. Mais esperto do que fazer. Caso contrário, a função retorna o produto fora da entrada e o resultado de chamar a função com um argumento que é menor por um. Muito bem, vamos experimentar a nossa função. E de fato, fatorial off três é seis. Agora vamos tentar com um número maior. Digamos que com então, Tudo bem, agora, vamos tentar com 20. E que tal 30? Ops, temos um erro. Isso ocorre porque o resultado seria maior do que o valor máximo que pode ser representado. Usando um inteiro de 64 bits não assinado, eu imprimir no local em 64 Max do conselho. Então este é o maior número que podemos representar usando um inteiro sem sinal de 64 bits, e o fatorial de 21 já é maior do que isso. Agora não há suporte para grandes inteiros no Swift. No entanto, há um grande protótipo no repositório rápido oficial. Você pode encontrá-lo na suíte principal. Rep. Oh, sob protótipos de teste, eu seleciono errado, em seguida, salvei a página como um arquivo fonte rápido. Em seguida, vou adicioná-lo ao nosso projeto de recreio. Nós não precisamos desta importação, e eu também me livro dos testes exceto este tipo de alias. Agora posso usar o grande Intertype. Então vamos refletor r função fatorial. Vou usar start para o argumento de entrada. Comece também para o tipo de retorno. Agora vamos experimentar nossa nova função. Ele já funciona com 30 para que possamos até aumentar muito mais e o resultado será um grande número como você verá no momento. Felizmente, veremos o tipo de início em breve na biblioteca oficial de peneiração. Até lá, você pode usá-lo, mas é por sua conta e risco. 16. Pitfalls de recisão: Rickerson é ótimo, mas não vem sem batida. Para nós, o maior problema é infinito. Ryker Shin. Vou ilustrar isso. Usando no projeto Exco Playground, eu implementar uma função que calcula o alguns fora dos primeiros e positivos inteiros. Chamo a função de ruim. Alguns dedos deixam claro que não é a abordagem certa para resolver esse problema. Eu vi você a solução certa que depende de uma fórmula simples em uma próxima lição para que alguns, exceto no parâmetro de entrada e fora do tipo int e retorna em inteiro, usarão uma abordagem recursiva. A função retorna, o alguns fora do parâmetro de entrada e o resultado de chamar-se com um argumento que é menor por um. Tudo bem agora, vamos tentar com, digamos, digamos, três eventualmente um erro de tempo de execução. Claro, para entender a causa raiz, vamos rapidamente recapitular como o Rickerson funciona. Cada vez que a chamada molestada ocorre um registro off. O contexto atual é feito e adicionado como um novo manípulo no topo da pilha, e cada vez que um carro retorna, o quadro superior é removido. A pilha é uma parte especial fora da memória usada para alocações estáticas rápidas. Cada aplicativo tem uma pilha, e os aplicativos de crédito Moody s têm uma pilha por thread. A pilha tem um tamanho finito. Assim, se continuarmos chamando funções aninhadas e nenhum desses retornos funções foram executados fora do espaço de pilha disponível. Quando a memória disponível para o cáustico é excedida, o atleta falha com um erro de estouro de pilha. Vamos inspecionar o nosso melhor. Alguma função. Não há nenhuma condição que impede a execução da chamada aninhada repetidamente. Vou mudar ligeiramente o tribunal para imprimir o valor do argumento de entrada sempre que chamarmos a função. Agora podemos ver claramente que a execução não pára depois de dois cursos recursivos como deveria. O que isso significa é que o contexto doméstico não são destruídos e os quadros de pilha não são removidos. Continuamos alocando memória na pilha sem a alocação, que eventualmente leva através da pilha. Exceção de estouro 17. Como evitar Recursion? infinita?: para evitar o infinito Ryker Shin. Cada função recursiva precisa ter pelo menos uma condição que impede o custo aninhado para si mesmo. Esta condição é um caso baseado em Deus. Então vamos voltar para o melhor alguma função e adicionar o caso base ausente. A questão é que apostar alguma causa em si como continuamos diminuindo, Thean colocar argumento e precisamos do caso base aqui. Essa é uma condição que faz a função retornar sem executar outra chamada recursiva . Só estamos interessados nos números inteiros positivos. Então, se o argumento de entrada é zero, podemos simplesmente retornar zero. Se eu executar a função após essa alteração, ela produz o resultado esperado. Mas essa verificação realmente funciona para todos os valores de entrada? Vamos verificar com a mente Swan. Não, desde que eu só verifico zero a função porque falha de tempo de execução para entrada negativa, também devemos garantir que a função realmente progride em direção ao caso base. Eu preciso modificar o caso base para que ele se encolhe não apenas o valor zero, mas também os valores negativos. Agora, esta declaração condicional funcionará. No entanto, uma declaração de guardas é um ajuste melhor porque nos força a sair da função Eu sei que algumas linguagens de programação têm construído em verificações para evitar estouros de pilha. Lembrem-se destas regras. Quando você implementar soluções recursivas em Swift e Jack, você funções recursivas completamente através de testes de unidade que acovardar também casos borda. 18. Seção 4: O poder dos algoritmos: nesta seção, vamos dar uma olhada mais de perto na importância e os benefícios de algoritmos e pensamento algorítmico que falamos sobre o grande ou notação na seção anterior. Vimos que a nossa escolha de implementar um problema pode fazer uma grande diferença quando se trata de desempenho e escalabilidade fora. Nossa solução é horrível. Pensar é a capacidade de abordar um problema e encontrar a técnica mais eficiente para resolvê-lo. Para demonstrar o poder dos algoritmos, vamos resolver os seguintes problemas. Nós calculamos o alguns dos primeiros e números naturais. Então vamos implementar a função que, dada uma matriz e o valor retorna os índices de quaisquer dois elementos distintos cujo alguns é igual ao valor alvo. Finalmente, vamos calcular o índice de equilíbrio dos homenageados. O equilíbrio ou índice de equilíbrio representa o índice que divide as matrizes de tal forma que a soma dos elementos que índices mais baixos é igual à soma dos itens em mais alto neste é que vamos usar uma abordagem ingênua primeiro, em seguida, implementar uma solução com eficiência em mente. Vou mostrar a vocês como alguns conhecimentos básicos de matemática e de recursos de linguagem e estruturas de dados podem nos ajudar a implementar uma solução mais limpa e mais desempenho. 19. Calcular soma (N): Nossa primeira tarefa é implementar a função, que calcula alguns dos primeiros números e naturais. Vamos começar com a abordagem ingênua. Então vamos implementar uma maneira mais eficiente de resolver este problema, usando uma fórmula que tem mais de 2000 anos de idade. Tudo bem, então vamos mudar para o nosso projeto de recreio de exclusão. Eu acho uma função chamada alguns, que leva um único argumento. Este argumento representa o número de números naturais que alguns queremos calcular os retornos funcionais, um inteiro sem sinal que dá a alguns nós implementar uma lógica muito simples. Nós resumimos todos os números, começando com um até o valor do parâmetro de entrada. E por causa desse loop, nossa função tem uma complexidade de tempo linear. Podemos confirmar isso chamando a função solar com constante aumento e valoriza a causa. Um log mostra que o tempo de execução aumenta linearmente com a entrada. Embora a disfunção faça o trabalho, há uma maneira melhor de calcular a soma do primeiro e dos números naturais. Vamos contar com uma fórmula simples. Dizem que Carl Friedrich Gauss encontrou esta relação na sua terra primitiva. No entanto, ele não foi o primeiro a descobrir esta fórmula. É provável que sua origem remonta às categorias, e era conhecida já no século VI. Antes de Cristo. Os benefícios de usar esta fórmula tornam-se evidentes. Se você verificar alguns exemplos para calcular alguns dos primeiros 3 números naturais, podemos apenas adicioná-los. Juntos obtemos os mesmos resultados usando a nova fórmula. À medida que o número aumenta, torna-se óbvio que a fórmula dá uma solução mais limpa e mais curta. Então vamos implementá-lo. Usando Swift, a função otimizada soma opera em tempo constante. O tempo de execução não depende da entrada. Vamos executar os mesmos testes de desempenho que fizemos para a alguma função. Os resultados provam que os tempos de execução não. Muito. Independentemente do tamanho da importação. Existem apenas algumas diferenças menores e insignificantes na faixa de microssegundos, mas não um grande benefício. Fora do algoritmo linear é o seu desempenho. Vamos comparar os dois métodos que alguns otimiza, mais eficiente, mesmo para valores menores, ea diferença apenas cresce com a entrada. Estes gráficos visualizam é os tempos de execução fora das duas funções. A função de tempo constante otimizada não depende da entrada, ao contrário da função alguma que é executada em tempo linear. Ao aplicar esta fórmula inteligente, conseguimos implementar uma solução com a maior complexidade de tempo. Na próxima palestra, vamos resolver um problema mais desafiador. 20. Desafio de correspondência de pares: Aqui está o nosso próximo desafio. Nossa tarefa é escrever uma função que, dada uma matriz e o valor alvo, retorne índices baseados em zero de quaisquer dois elementos distintos que alguns são iguais ao alvo. Alguns. Se não houver tais elementos, a função deve retornar. Neil, por exemplo, para a área dos números 12234 E o valor alvo para a nossa função deve retornar os índices de queda 12 ou 03 Primeiro, vamos implementar a solução que depende de iterações ácidas porque das repetições desagradáveis. Este algoritmo tem uma complexidade de tempo quadrático. Então vamos chegar a um algoritmo que opera em tempo de Lena em vez de tempo quadrático. Certo, hora de fazer alguma codificação. Como de costume, implementamos a abordagem da força bruta. Primeiro, passamos pela matriz e verificamos todos os valores a partir do índice externo, analisamos o resto da matriz. Se encontrarmos um número tal que os dois números somam ao alvo, devolvemos o topo. Enquanto continuamos a iterar através do saberi. Esse algoritmo usa dois loops aninhados, o que significa complexidade de tempo quadrático. Para ser preciso. Esta função tem um pior tempo de complexidade fora e quadrado, mais e dividido por dois. Onde N é o tamanho fora do ímpeto? Três. Não é n ao quadrado, desde Viena olhar não iterado através de toda a matriz. Vamos passar pelos passos para encontrar esta fórmula. O loop externo iterado através de toda a matriz, que dá um orations os restaurantes de loop interno e menos uma vez Força do que l menos duas vezes e assim por diante. Quando o Loop externo Richard o penúltimo índice, o loop interno em reitera quer descobrir o total que as orações realizam no loop interno , temos que calcular a soma dos números primeiro e menos um. Podemos usar a fórmula que aprendemos na palestra anterior. Calcule a contagem de loop interno que é um menos uma vezes e menos um mais 1/2, que dá n menos uma vezes e mais para agora juntos número total de orações. Devemos adicionar a contagem dos loops externos para assim que nossa função tem uma complexidade de tempo fora e quadrado, mais e ou dois. Agora vamos implementar uma solução, que não depende de loops aninhados. Em outras palavras, vamos evitar assustar a taxa sábia para encontrar números que somam ao valor alvo . Vamos usar um único loop para restaurantes por todo o caminho. Para cada número, verificamos se a diferença entre o valor alvo e o número dado pode ser encontrado no registro de dependência. Se a diferença for encontrada, nós temos nossos dois números e nós retornamos o topo de com os índices como nós armazenamos o índice atual, a diferença é a chave e nós comê-lo ainda mais não, que ambos dicionário inserção e pesquisa acontecendo em tempo constante. Portanto, essas operações não afetarão a complexidade do tempo de nossa função. Conseguimos reduzir o tempo de complexidade para fazer o pedido, e porque só analfabetos uma vez através do array agora vamos comparar o desempenho das duas funções. Primeiro, executamos nosso teste com uma matriz que contém 10 introdução aleatória. A função otimizada geralmente funciona melhor do que aquela com complexidade de tempo quadrático . No entanto, a diferença de velocidade não é tão convencido Singer. Para 50 itens, começamos a ver diferenças visíveis. Os benefícios da complexidade do tempo linear são bastante evidentes. Os resultados falam por si mesmos à medida que aumentamos o tamanho fora do array ainda mais. Na próxima palestra, vamos resolver outro problema interessante chamado Índice de Equilíbrio 21. Encontre o índice de equilíbrio: na demonstração a seguir, vamos construir um dedo do pé função, Encontrar os índices de equilíbrio de Honore. O Índice de Equilíbrio de Honore é um índice tal que a soma dos elementos em índices mais baixos é igual à soma dos elementos em índices mais altos. Por exemplo, em Honore A, com os números menos três a menos 21 e menos dois um é um índice de equilíbrio porque o elemento que índice zero é igual à soma dos elementos que índices dois e três e quatro dois é também no índice de equilíbrio. Porque a soma dos elementos que neste zero e um é igual à soma dos elementos que neste é três e quatro, vamos implementar a função que dado Honore retorna Theokoles, Índices de Librium ou Neil se a área não tem índice de equilíbrio. Primeiro vamos implementar uma solução, que usa dois loops aninhados. Então eu vou mostrar a vocês uma maneira de otimizar nosso algoritmo aplicando alguma matemática básica, vai chegar a um algoritmo que executa em tempo linear. Agora vamos mudar para a quadra X. A função de equilíbrio usa três loops os restaurantes de loop externo para todos os elementos fora teoria, precisamos de loops internos para descobrir se o índice atual grande pelo loop externo é um índice de equilíbrio ou não. O primeiro no loop rastreia alguns dos elementos em índices mais baixos. O segundo loop interno manter o controle de alguns itens off em índices mais altos. Em outras palavras, com a teoria do plead na posição fora do índice externo, então comparamos alguns dos elementos fora dos dois Sabri. Se as somas são iguais, encontramos um índice de equilíbrio, e adicionamos à teoria dos índices à medida que continuamos Iterando ainda mais, a pior complexidade de tempo fora desta solução é quadrática. Atualizar as somas esquerda e direita usando para loops internos é uma abordagem simples, mas também muito ineficiente . Vamos tentar encontrar uma solução que não exija loops aninhados. A idéia é juntos nos disse alguns da matriz. Primeiro, usamos o reduzido ou um método para calcular a soma de todos os elementos em teoria, então nós Itália, através de toda a matriz a esquerda. Alguns são originalmente inicializados para zero. Continuamos atualizando a esquerda, alguns adicionando elementos T como iterado através da matriz podemos obter o alguns dos elementos do resumo direito subtraindo os elementos um por um da soma total. Com este algoritmo, só precisamos olhar uma vez através do array. Esta função tem uma complexidade de tempo linear ordenada fora para terminar por causa da função reduzida e do loop. Agora vamos correr os nossos pobres quatro meses, Tess por cinco itens. A variante otimizada tem um desempenho cerca de duas vezes melhor e mais de 20 vezes melhor para 50 itens por ferimentos fora de 200 itens. A função otimizada de equilíbrio é executada cerca de 1000 vezes mais rápido do que a função, que usa loops aninhados. A diferença cresce rapidamente com o tamanho de entrada para arrays maiores. Encontrar índices de um assustador Thea com a variante de otimização em que leva uma fração fora do tempo de execução fora da abordagem de força bruta como esperado, a função com complexidade de tempo quadrático é mais sensível para importar tamanhos de dados do que o função com complexidade de tempo linear. Este é outro exemplo que demonstra a importância de encontrar o algoritmo certo 22. O poder dos algoritmos - resumo: nesta seção, vimos alguns exemplos práticos sobre a resolução de problemas usando duas abordagens diferentes. As implementações da faca produziram os resultados certos. No entanto, eles começam a mostrar suas fraquezas à medida que o tamanho de entrada fica maior. Utilizando técnicas mais eficientes, reduzimos consideravelmente o tempo, a complexidade e , consequentemente, , consequentemente, o tempo de execução das nossas soluções. Chegar com o algoritmo ideal requer pesquisa e compreensão mais profunda do problema. Estamos tentando resolver engrenagens de metanfetamina e a capacidade de aplicar os recursos fora da linguagem de programação dada será mais feliz em criar algoritmos mais eficientes. A complexidade centavo muitas vezes algoritmo, é crucial quando se trata de desempenho. Faça o seu melhor para evitar complexidades polinômios e piores tempos. loops Nassib devem ser sempre um sinal de aviso sempre que você os encontrar. Pense em outras alternativas para resolver esse problema em particular. Para recapitular, você deve destacar os gargalos de desempenho. Usando comentários dedicados, implementar testes de unidade e desempenho, eles foram surgidos. As questões que, de outra forma, permaneceriam escondidas finalmente tentam resolver o problema sem depender das reiterações da NASA, se possível. Agora sabemos o que é a notação maior. Nós também estamos cientes dos benefícios de algoritmos e pensamento algorítmico Vamos prosseguir com o estudo de algoritmos na próxima seção, vamos dar uma olhada mais de perto nos algoritmos básicos de classificação mais populares. Vamos analisar como os algoritmos de classificação funcionam, e vamos implementá-los a partir do zero usando o Swift. 23. Seção 5: genéricos: antes de mergulharmos mais profundamente em algoritmos, é importante falar sobre as estruturas de dados tópicos relacionados. Estruturas de dados são contêineres que contêm os dados usados em nossos programas. A eficiência dessas estruturas de dados afeta todo o sistema de software, por isso é importante entender como eles funcionam e qual deles escolher para a tarefa específica . Nesta seção, vamos falar sobre genéricos e o edifício. Tipos de coleção Swift Generics são os meios para escrever código não só útil, mas também reutilizável . Há também usado para implementar estruturas de dados que não são restritas apenas um tipo de dados . Então vamos dar uma olhada mais de perto no quinto tipo de coleção do prédio. Vamos falar sobre o array, o conjunto e o tipo de dicionário. 24. Por que genéricas?: Os genéricos estão no núcleo da biblioteca padrão rápida. Eles estão tão profundamente enraizados na língua que você não pode evitá-los. Na maioria dos casos, você nem vai notar que você está usando genéricos. Para ilustrar a utilidade dos genéricos. Tentamos resolver um problema simples. Digamos que precisamos criar tipos que mantêm pares de valores diferentes. Assumindo que precisamos de um tipo de par que contenha duas cordas, poderíamos criar uma estrutura como esta. Em seguida, precisamos de um par segurando para inter valores. Então, declaramos nosso tipo de reposição. Então também precisaremos do DYP, que tem que flutuar. Aqui vamos nós. Que tal um par que tem propriedades de dados? Nós cumprimentamos mais uma estrutura de pares chamada par de dados. E se precisarmos do par duplo de cordas, criamos o tipo apropriado, certo? Poderia ser mais simples? Agora podemos usar nossos tipos recém-criados sempre que precisarmos deles. Só devemos lembrar os nomes deles. Sempre que precisamos de um novo tipo de par que simplesmente criamos. Este é mesmo o caminho a percorrer? Definitivamente não. Temos que parar a explosão antes que ela saia do controle. 25. Tipos genéricos: Não seria? Porque o dedo do pé tem apenas um tipo, que pode funcionar com qualquer valor. Tipos genéricos vêm para o resgate. Usando genéricos, podemos definir uma estrutura de par que pode ser usado com qualquer tipo que usamos lugar clima em vez de tipos de concreto para as propriedades na estrutura T um e T dois R ordens policiais que podem ser usadas em qualquer lugar dentro dos tipos definição. Além disso, nós simplesmente chamamos nosso par atingido. Como é um tipo genérico, não precisamos especificar os tipos suportados no nome da nossa estrutura. Agora podemos criar pares de qualquer tipo usando a seguinte sintaxe. Podemos até pular o lugar onde há tipos. O compilador é inteligente o suficiente para descobrir o tipo com base no tipo de argumento. A inferência funciona examinando os valores fornecidos. Por que compilar o tribunal? Em Swift, podemos definir nossas classes genéticas, estruturas ou enumeração tão facilmente. Tudo bem, vamos o que falta marcado. Vou tornar os benefícios dos tipos gênicos ainda mais óbvios. Então esta foi a nossa primeira tentativa ingênua de criar os tipos de pares. Um monte de código redundante. Agora, vamos declarar a versão genérica com a estrutura do par no lugar. Podemos excluir todas as estruturas específicas de pares. Agora que eles se foram, obtemos um erro de compilador. Podemos, não é? Conserte isso. Eu vou substituir todas as referências aos tipos antigos com a contrapartida genérica que os tipos genéricos têm que parou a explosão de tipo. Nosso código não só se tornou mais curto, mas também é re visível. Em seguida, vamos falar sobre funções genéricas. 26. Funções genéricas: funções genéricas e métodos são outro recurso poderoso fora da linguagem rápida. Uma função genérica ou método pode trabalhar com qualquer tipo que é podemos evitar duplicações e código de limpeza direito. Vamos começar com o desafio de programação que precisamos implementar um método que faz, se para valores são iguais. Primeiro, definimos a função de igualdade fácil para cordas bastante simples. Então precisamos do mesmo recurso para tipos duplos, não é grande coisa. E quanto a datas? Felizmente, isso também não vai demorar muito para ser implementado. Em seguida, também precisamos dizer se as instâncias de dados são iguais feitas até agora. Você deve ver onde isso vai dar. E se você foi a lição sobre tipo explosão, você sabe o que eu estou prestes a dizer. Este não é o caminho a seguir. Implementar uma nova função para cada novo tipo leva a um código redundante muito fora. Essa base judicial é difícil de manter as notícias. Devemos sempre evitar repetições de código e genéricos. Ajude-nos a resolver este problema também. Tudo bem, vamos criar a função genérica é igual. A sintaxe para escrever uma função genérica é semelhante ao que usamos para declarar tipos genéricos . Nós especificamos o lugar onde eles são tipo entre suportes de raiva. Após o nome da função ou método, podemos nos referir a este lugar onde há tipo no argumento, menos ou em qualquer lugar no corpo funções. Se compilarmos nosso código como ele está agora, obtemos um erro. Isso ocorre porque o compilador não sabe como comparar duas instâncias fora do local. Se tipo, devemos garantir que o tipo implementa o igual ao operador que está lá. Para adotar o protocolo de lei do Equador deve implementar o igual ao operador, por isso devemos impor uma restrição de tipo. Restrições de tipo especificadas que o tipo deve estar em conformidade com um protocolo específico ou herdar de uma classe específica. Vamos adicionar a restrição de tipo equitativo. Isso limita os tipos que podem ser usados como argumentos em nossa função. Nós nos livramos do erro do compilador. Agora, a facilidade genética igual função só pode aceitar instâncias fora de tipos que adotam o protocolo equitativo. O contato é obstrução que não está em conformidade com o equador, onde o protocolo que nosso código não irá compilar se tentarmos. Foi a função central fácil com instâncias de contato. Então vamos adicionar a conformidade de protocolo equitativa para adotar o equador, onde protocolo temos que implementar o operador de reboque igual como um membro estático. A implementação é simples. Verificamos se as propriedades fora dos dois argumentos correspondem. O Protocolo Equitable também define o operador não igual. Não precisamos implementá-lo, embora a biblioteca padrão forneça a quarta implementação. Isso causou o operador de reboque igual personalizado e os gays. O resultado. Podemos aplicar restrições de tipo, também tipos genéricos. Você pode se lembrar do par genérico atingido que implementamos na lição anterior. Digamos que queremos limitar os tipos daqueles que implementam o protocolo comparável . Aqui está o que devemos, certo. Com essa restrição de tipo, só podemos criar instâncias de par fora do tipo que adotam o protocolo comparável. Genéricos são super usados para, e Swift torna mais fácil para nós implementar e usar tipos e funções genéricas. Nas seguintes lições foram indo dedo do pé encolher o construído em tipos de coleção rápida 27. Seção 6: tipos de coleta rápida: bem-vindo a outra seção dos algoritmos rápidos e pontuações de estruturas de dados nesta seção. Vamos dar uma olhada mais de perto no quinto tipo de coleção do prédio. Sweet fornece três coleções primárias. Falamos sobre a matriz, que está na sequência de ordem de itens. O conjunto, que está em uma nova sequência de ordem fora de valores únicos, eo dicionário que permite que a nossa loja e excesso de pares de valor chave no Swift. A matriz, o conjunto e o dicionário são implementados como tipos genéricos, como vimos na seção sobre genéricos. Isso oferece grande flexibilidade, pois podemos usar qualquer tipo com as coleções genéricas. Eles podem armazenar instâncias fora de óculos, estruturas e imolações, ou qualquer tipo de construção como int float, duplo e assim por diante. Tudo bem, vamos começar com a teoria. 28. A matriz: valores da loja de elogios fora do mesmo tipo em uma ordem específica. Os valores não devem ser únicos. Cada valor pode aparecer várias vezes. Em outras palavras, poderíamos definir a matriz como uma ordem, lantejoulas fora elementos não únicos. Criamos no raio usando a seguinte sintaxe. Uma vez que é um tipo genérico, devemos fornecer o tipo que são um ancinho na loja. Esta é uma matriz fora em tipos. O que isso significa é que só podemos usar o nosso A dentro. Há uma maneira mais curta de definir matriz, colocando o tempo entre colchetes angulares. Esta é a forma abreviada, e é a maneira preferida de definir Honore. Na verdade, não há nem certeza de sua maneira de criar uma matriz de ins para certos tipos. Também podemos contar com inferência de tipo rígido, dedo do pé trabalhar o tipo de matriz. Agora vamos falar um pouco sobre tipo inferência rápida parabéns, o tipo baseado no poço que fornecemos, o que pode nos salvar de um monte de digitação. No entanto, inferência de tipo tem suas limitações. Por exemplo, se definirmos a nossa distância assim, o motor de inferência de tipo assumirá que é uma matriz de duas vezes a refinaria off floats , devemos fornecer explicitamente o tipo de fluxo. Cada item em Honore tem um índice associado a ele. Os índices começam em zero, e seu valor é implementado para cada item subseqüente. Então, para o nosso exemplo original, os índices se parecem com isso. Podemos, ou através da teoria e imprimir os índices usando o índice de teoria fora do método de instância Tudo bem Menos do que isso em código X. Aqui está um registro do console. Saber que o índice off retorna o primeiro índice onde o valor especificado aparece em teoria, é por isso que temos o mesmo índice para um e dois. Outra maneira é usar as matrizes para cada método. Este método executado divulgação em cada elemento na mesma ordem que um loop for in, e o resultado é o mesmo que com o exemplo estrangeiro. 29. Acessando a matriz: podemos acessar os elementos no índice Rabei. A matriz tem que conveniência o excesso de feridas para o primeiro e o último elemento. Não, aquele primeiro e último retorno. Valores opcionais. Se as matrizes vazias, seu valor será Neil. Não temos essa rede de segurança ao acessar o array pelo índice em torno do tempo que ocorre uma falha. Se tentarmos recuperar um valor usando no índice inválido, podemos evitar falhas verificando se o índice está dentro dos limites. Se um índice é maior do que o tamanho fora do raio, ele vai apontar para o dedo do pé além do último item. Além disso, o índice não deve ser um número negativo. Podemos inventar uma forma mais curta. O raio tem uma propriedade chamada Índices que detém, bem os índices reais para o dado Ray. Se ele contém o índice dado, então é válido para empurrá-lo ainda mais. Vamos criar um operador de índice seguro personalizado. Implementamos o operador em Honore. Extensões de extensão e operadores personalizados são realmente poderosos. Eles nos deixam em operadores para tipos existentes sem modificar seu código 30. Modificando a matriz: até agora, vimos como acessar os elementos de Honore neste vídeo vai olhar para como modificar a matriz para alterar o conteúdo de Honore após sua criação. Devemos atribuí-lo a uma variável em vez da constante. É assim que podemos criar uma matriz mutável. Instância. A teoria expõe diferentes instâncias. Métodos para adicionar novos valores Podemos. Ele estava com o dedo do pé. Adicionar um novo elemento para o final de Honore para inserir no elemento que são dadas posição usado a inserção. Na instância. Método. O novo elemento é inserido antes do elemento no índice atual. Todos os elementos após o índice dado são deslocados. Uma posição à direita. Se você passar no último índice, o novo elemento será abandonado. Deite o pé da matriz. Ao usar, insira em, certifique-se de que o índice é válido. Caso contrário, você acabará no erro de tempo de execução. Agora, para remover um elemento de uma matriz, podemos usar o removido. Na instância, método. Depois que o elemento é removido, o espaço é fechado. Eu sei que o índice que passamos a remover esse método deve ser válido ou porque em torno do tempo , erro Deus remover todos. Se você quiser se livrar de todos os elementos na matriz. O método tem um parâmetro de capacidade de manutenção, que é definido para forçar pelo quarto. Você pode querer manter a capacidade se você planeja re foi a corrida em breve, a matriz não precisará realocar memória, que pode ser uma boa otimização de desempenho agora, embora a capacidade é mantida, não podemos reutilizar o velho. O Indo está acessando a área onde está obsoleta. Índices causa no acidente instantâneo como regra geral. Verifique sempre se o índice está fora dos limites antes de acessá-lo. Há outros métodos. Remover primeiro, remove e retorna o primeiro elemento, enquanto remover lista, remove e retorna. O último elemento. Não vá remover primeiro ou remover por último em um vazio ou um como isso causaria, como você já deve saber. Erro de tempo de execução Falamos sobre alguns dos mais frequentemente foi métodos de matriz. Sugiro que você abaixe os projetos de amostra e comece a mexer com os raios para recapitular. Parades, armazenar valores fora do mesmo tipo na sequência de ordem. Teoria dos judeus. Se a ordem dos elementos for importante e se os mesmos valores aparecerem várias vezes se a ordem não for importante ou se os valores tiverem de ser únicos. Você deve preferir usar um conjunto. Falaremos sobre cenários nas próximas lições. 31. O conjunto: vimos que o ancinho e armazenar elementos em uma determinada ordem, podemos até ter dificuldade em honoree. E se você precisar de uma coleção que garanta a singularidade de seus elementos? O set é a resposta. Defina valores exclusivos da loja sem pedidos e um determinado valor só pode aparecer uma vez. Além do conjunto expõe usado para operações de conjunto matemático como união e subtrair, podemos declarar um conjunto usando a seguinte sintaxe. Eu sei que você não pode usar o formulário abreviado como fizemos para um aumento. Se o defendermos assim, o motor de inferência não consegue descobrir. Se queríamos instância você para definir ou melhor Honore, devemos especificar que precisamos de um conjunto. No entanto, inferência de tipo ainda funcionava para os valores usados no conjunto. Se inicializarmos o conjunto com uma matriz desligada em pequenos erros, o motor de inferência tipo irá inferir o tipo int. E se ele estava flutuando ponto literalmente, o in for type para os valores será o dobro. Agora vamos esclarecer as principais diferenças entre os conjuntos no aumento. Meu olhar para essas diferenças será capaz de escolher a certa, as primeiras diferenças fundamentais que o conjunto não permite duplicatas. Vamos dar uma olhada em um exemplo se declararmos Honore como este vai conter quatro extremidades com o valor um. Onde é o conjunto declarado com os mesmos liberais terá apenas um valor. Os valores redundantes são desnatados. A outra grande diferença é que o conjunto não fornece a ordenação definida para seus elementos. Por exemplo, o cinza a seguir irá imprimir seu conteúdo na ordem dada. No entanto, para dito, definido com os mesmos valores, a ordem é indefinida. Podemos gerar sobre os valores em um conjunto usando um loop for in. Lembre-se, o conjunto não define a ordenação específica fora de seus elementos. Assim, não assuma nada sobre a ordem em que os elementos são retornados se necessário. Iterar uma ordem específica chamada o Método Sordid, assim fez retorna os elementos fora do conjunto como uma matriz classificada usando o operador menor que. Esta é a saída. Também podemos usar o método de coleta de quatro H com conjuntos. Este método executa seu fechamento em cada elemento no conjunto 32. Acessando e modificando o conjunto: Agora que sabemos como criar um conjunto, vamos falar sobre acessar e modificar seu conteúdo. Ao contrário da teoria, o dito não tem índices, podemos usar o método contém instância para verificar se um valor existe no primeiro conjunto contém retorna um negrito no valor para que possamos usá-lo na lógica condicional, assim como em este exemplo, se o elemento não puder ser encontrado ou se o conjunto estiver vazio. Contém força de retornos. Falando de conjuntos vazios, podemos verificar se um conjunto tem elementos através dessas propriedade vazia. Alternativamente, podemos usar a propriedade sets count. Como você deve ter adivinhado viragens país. O número de elementos no conjunto sabe que as propriedades de contagem de conjuntos e capacidade podem retornar valores diferentes. País transforma o número de elementos existentes no conjunto, enquanto a capacidade mostra quantos itens ele pode armazenar sem alocar novo armazenamento. Falarei sobre isso em um momento. Utilizado o método inserções, na instância, para adicionar novos elementos ao conjunto. Para remover elementos de um conjunto, podemos chamar o método remove. O carro não faz nada se o elemento não estiver no mínimo, o método remove retorna o elemento que foi removido do conjunto. Podemos usar esse recurso para verificar se o valor foi realmente exultante para remover todos os elementos em um carro conjunto, remover todos os conjuntos, remover o nosso método tem um parâmetro de capacidade de manutenção, que é definido para forçar pelo quarto. Ele tem o mesmo efeito que para um aumento, definindo o valor de manter a capacidade como true sem o compilador para manter a memória SATs depois de remover seus elementos, eles não precisarão realocar memória em seu próximo uso. 33. Definir operações: o conjunto expõe métodos úteis que nos permitem executar Operações Fundamentais União cria um novo conjunto com todo o elemento nos dois conjuntos. Se os dois conjuntos tiverem elementos em Onley comum, uma instância aparecerá no conjunto resultante. Não que 35 e sete podem ser encontrados em ambos os conjuntos. Mas o conjunto resultante não conterá duplicatas. O resultado da chamada da instância do conjunto de interseções. Método é um conjunto, que foi os elementos que aparecem em ambos os conjuntos. Também podemos subtrair um conjunto de outro. O resultado conterá os valores que estão apenas no conjunto de origem e não no conjunto subtraído. Os retornos do método de diferença simétrica são definidos com o elemento que estão apenas em qualquer um dos conjuntos, mas não ambos. O conjunto expondo muitos outros métodos úteis, como os que nos permitem testar a igualdade e a adesão. Eu sugiro que você para baixo com os projetos de amostra e começar a experimentar com conjuntos 34. O Protocolo de Hashable: Oi lá. Vamos falar sobre o protocolo mashable. Primeiro, vou criar uma estrutura muito simples. Esta estrutura tem apenas uma string de tipo desligado corretamente. Vamos chamá-lo de fogo de identidade sem instruir o lugar. Poderíamos criar, por exemplo, Honore. Vou usar o formulário abreviado para declarar a teoria fora. Simples atingiu USOC. E vamos adicionar um simples golpe com a identificação de seu I D. Este ouro compreende muito bem. Não temos problemas. Agora vamos tentar fazer o mesmo. Mas desta vez vou declarar um conjunto. Infelizmente, não há nenhuma maneira de que era uma forma abreviada para um conjunto porque o compilador não tem como distingui-lo de Honore. Basicamente, eu tenho que dizer ao compilador que é um set off determinado tipo. Aqui vamos nós. Agora. Se eu tentar compilar meu código, recebo um erro. O compilador diz que o nosso tipo não está em conformidade com o possível protocolo. Tudo bem, o que isso significa? O conjunto é um tipo especial de coleção rápida. Ao contrário de raise, um conjunto não pode ter duplicatas. Para verificar se há duplicatas, o conjunto deve ser sobre o tipo. Isso tem uma maneira de dizer se uma instância é exclusiva. Swift usa um valor de hash para esta finalidade. O valor de hash é um valor exclusivo fora do tipo IND que deve ser igual se dois valores forem iguais e rápidos. Nossos tipos básicos de construção são hackable, então podemos usar uma corda um touro no fim ou um duplo no set. Aqui vamos nós. Então, se eu declarar meu conjunto assim como este conjunto duplo o compilador não vai reclamar mais uma vez que double fornece um valor de hash. Agora, para que nossa estrutura simples funcione com o conjunto, devemos confirmar o Protocolo de Hassiba. Felizmente, isso não é grande coisa. Acabei de ter um conformers de moda. E se você verificar o possível protocolo, ele tem uma única propriedade. É uma propriedade acessível somente leitura chamada valor hash. Portanto, este valor de hash deve ser único, vez que a nossa estrutura simples tem apenas uma propriedade off type string e string é um tipo de construção que já implementa o protocolo hashiba. Implementar a propriedade de valor de hash é bastante simples. Tudo bem, vamos tentar compilar. Está frio agora ainda temos um problema. Vamos checar duas vezes estava acontecendo aqui. Muito bem, são um tipo de ataque simples também deve estar em conformidade com o Protocolo Equitable. Por que é isso? Como a Hashiba herda de protocolo degradável e se um protocolo herda de outro , todos os tipos de conformidade também devem implementar os requisitos definidos nesse protocolo. Então, como voltar em conformidade com o peso do protocolo também não é um grande negócio. Temos que implementar o operador de reboque igual, que é um método estático que faz se duas instâncias fora do tipo dado são iguais ou não. Consideramos instâncias simples atingidas para ser igual se eles são identificar IRS são iguais agora nosso código deve compilar sem erros. Na verdade, a questão desapareceu para resumir. Haverá casos em que teremos de adoptar o Protocolo Hashiba. Se você precisa garantir que um determinado valor é único preto, por exemplo, ao criar um conjunto fora de nossos tipos ou usá-los como chaves para um dicionário, então devemos adotar o hash Hable Protocol Para confirmar o protocolo habitável são digite deve implementar um valor de hash somente leitura chamado corretamente. Além disso, porque a moda confirma o Protocolo Equitable, devemos implementar o operador de reboque igual 35. O dicionário: o dicionário, também conhecido como lojas de mapa de hash. Pares de valor chave usar este tipo de coleção se você precisa olhar para cima muito, foi baseado em sua identificação IRS. Cada valor deve ser associado a uma chave que seja exclusiva. A ordem das chaves e valores é indefinida. Assim como os outros tipos de coleção rápida, o dicionário também é implementado como um tipo genérico, muito grande um dicionário. Devemos especificar a chave e o tipo de valor. É assim que podemos criar um dicionário vazio. Outra maneira é usar a sintaxe inicial de Isar. Podemos inicializar um dicionário com um dicionário. Literal Swift pode inferir o tipo fora das teclas e os valores com base no líder. Ao criar um dicionário, o tipo de chaves e valores deve ser consistente. Por exemplo, Archies são um vintage seu tipo e todos os valores fora do tipo. Tipo de string Inferência não funcionará se o tipo fora dos líderes do dicionário for misto. O compilador nos pede explicitamente no tipo anotações se realmente queremos declarar um dicionário hetero gênio, e em certos casos você pode querer fazer isso. Por exemplo, ao converter cargas úteis do Jason ou Listas corretamente, o dicionário tipo não funcionará. O Dicionário Gênio da História Maior. As chaves devem estar em conformidade com o hash about protocolo. Como vimos na palestra anterior, O Protocolo Hashiba define o requisito de propriedade chamado valor de hash. A propriedade de valor de hash deve retornar um valor exclusivo para uma determinada instância. Não há duas instâncias diferentes devem ter o mesmo valor de hash. O Swift Standard Library tem um tipo chamado Any hash a ball any hash a book e mantém o valor fora de qualquer tipo em conformidade com o hash about protocol. Este tipo pode ser usado como um super tempo para chaves em dicionários hetero gênio para que possamos criar um cabeçalho. coleção de Virginia como este qualquer heritable é uma estrutura que nos permite criar o tipo levantado valor hashem que envolve a instância dada. Isto é o que acontece nos bastidores. Na verdade, esta versão iria compilar muito bem se nós digitá-lo em X frio. Mas a sintaxe abreviada é obviamente mais curta e mais legível. Qualquer hash que uma propriedade baseada em barramento representa do valor RAB, ele pode ser convertido de volta para o tipo original, usando o como condicional como ou força como operadores de conversão 36. Acessando e modificando o dicionário: podemos acessar o valor associado a um dado ele usando a sintaxe subscrito. Nós também pode iterado sobre os pares de valor de chave fora de um dicionário usando um loop for in. Como se trata de um dicionário, os itens são retornados como um valor de chave superior. Podemos aceitar a propriedade de chaves dicionários para recuperar suas chaves. A propriedade valores do dicionário. Retornamos seus valores para adicionar um novo dedo do pé item, o Pictionary usar uma nova chave como o índice subscrito e o assiná-lo um novo valor. Para atualizar no item existente, podemos usar a sintaxe subscrito com uma chave existente. Alternativamente, podemos chamar o valor de atualização para o método chave. Este método atualiza o poço que você na chave tradicionalmente perdoada. Se a chave não existir, ela será um novo par de valores de chave para o dicionário. Você pode remover um valor de um dicionário atribuindo próximo para sua chave. Podemos alcançar o mesmo resultado ainda com mais digitação. Por que são o valor de remoção para o método chave Para apagar o dicionário, carro removido, todos remover. Tudo tem um parâmetro keep capacity, que é definido como false pelo quarto. Se você melhor durante a operação, preserve a capacidade fora do subjacente antes. Esta é uma otimização de desempenho. Se você planeja reutilizar o dicionário, 37. Seção 7: classificação básica: nesta seção, vamos falar sobre algoritmos básicos de classificação. Estes algoritmos estão no ponto de partida essencial para resolver problemas de forma elegante e eficiente. Compreender Thean er funcionamentos e saber como implementar os algoritmos básicos de classificação dá-lhe uma base forte construção de outro, algoritmos mais sofisticados para cada algoritmo. Vou explicar como funciona, e mostrarei a vocês como implementá-los do zero. Usando a última versão 50, vamos usar um excelente site classificando 0.80 para visualizar como o algoritmo funciona . Tudo bem, então o que está ordenando? Em primeiro lugar, a classificação é uma técnica para organizar dados em uma sequência lógica. De acordo com algumas regras bem definidas, trabalhar com dados classificados é muito mais eficiente do que acessar elementos em uma sequência não ordenada . A classificação tem um quilo em processamento de dados comerciais e computação científica. Vamos começar nossa jornada para a área, tirando algoritmos de classificação estudando três métodos elementares de classificação. classificação de seleção funciona selecionando o menor item e substituindo-o pelo anterior . Este algoritmo tem uma complexidade de tempo quadrático, e é um dos algoritmos de classificação de inserção simples como seu nome States funciona inserindo elementos em seu lugar apropriado para criar espaço para o item atual, elementos maiores devem Mova-se. Uma posição à direita. Classificação de inserção também tem complexidade de tempo pior quadrático. No entanto, o desempenho da fonte de inserção é amplamente afetado pela ordem inicial fora dos elementos na sequência. Barbara Sort. Este algoritmo funciona avaliando repetidamente itens adjacentes e suando sua posição se eles estão na ordem errada. O tipo de bolha é fácil de implementar, mas também é bastante ineficiente. Sua média e pior caso complexidade são ambos quadráticos. 38. Classificação de seleção: é um dos algoritmos de classificação mais simples. Começa por encontrar o menor item e trocá-lo com o 1º 1 Então ele encontra o próximo item menor e troca-o com o segundo item. O processo continua até que toda a sequência seja classificada. Na demonstração a seguir, vamos implementar o algoritmo de classificação de seleção usando o Swift três. Analisaremos a complexidade do tempo desse método e visualizaremos como ele funciona. É hora de fazer alguma codificação, então vamos qual Toe X ouro? A função de classificação de seleção leva uma matriz de inter apenas como entrada e retorna a cópia sórdida fora da matriz de importação. A classificação só faz sentido se o IRA tiver pelo menos dois elementos. Caso contrário, acabamos de devolver uma cópia do Re original. Em seguida, fazemos uma cópia do Array. Vamos classificar o conteúdo desta cópia e devolvê-lo da nossa função. A função tem dois loops os restaurantes Loop externos através de cada elemento, e mantém o índice, o que nega a porção sórdida fora da matriz. O loop interno encontra o menor número no resto da matriz para cada elemento. A função troca de posições com o menor valor do restante da teoria, dado o não-ordenado ou um 1 a 430 O Loop Exterior escolhe o primeiro elemento, que é um. Em seguida, o loop interno encontra o número mais baixo no resto da matriz. Como zero é menor do que um, a posição fora dos dois elementos é trocada. Agora temos o primeiro elemento na porção ordenada fora da matriz, que agora se torna 0 a 431 O loop externo é o próximo elemento para o loop interno encontra o menor número a partir da próxima posição. Um é menor que dois, então sua posição é trocada. Nosso início não tem elementos muito sórdidos. Quatro é grande pelo laço externo. Em seguida, o loop interno encontra o número mais baixo, que é para uma vez que dois é menor que quatro. Eles são esfregados, e nós temos 01234 O loop externo escolhe o próximo elemento, que é livre. O resto da taxa se esconde. Apenas um elemento quatro não é menor que três, então sua posição não é trocada. Finalmente, temos nossa matriz sórdida. 01234 Agora vamos analisar a complexidade do tempo fora do algoritmo de classificação de seleção, a teoria da fonte do algoritmo da esquerda para a direita, o tempo de execução é afetado pelo número off swaps e compara o número de trocas depende do ordem original dos elementos. O pior caso é quando a matriz é recompensas classificadas. O número de swaps será igual ao número off elementos. Em teoria, entanto, a complexidade do tempo fora do tipo de seleção é dominada pelo número de compara quatro Sob dia com um elemento o loop externo, analfabetos e mentes uma vez que o loop interno reitera e menos duas vezes primeiro do que e meu três vezes e assim por diante. Quando o loop externo atinge o penúltimo índice, o em um loop em analfabetos quer. Isso significa que temos um menos um mais e menos para mais e menos três e assim por diante, mais uma iterações no total. Se tivéssemos o número fora do pior caso. Weps, a complexidade do tempo torna-se e mais e menos um mais e menos para mais e menos três e assim um mais um, que dá n Vezes n mais um ou dois que é n ao quadrado, mais um sobre para, se você vai estar se perguntando, como conseguimos essa fórmula, eu sugiro que você assista a palestra sobre complexidade de tempo constante. Se a entrada já estiver classificada, o número de swaps será zero. Assim, a complexidade torna-se um vezes e menos um ou dois ou em forma mais curta e quadrado menos e mais até agora. Vamos fazer alguns testes de desempenho. Criamos relançamento com 10 101.000 elementos, respectivamente. Os resultados exibidos no conselho confirmaram a complexidade do tempo quadrático do algoritmo de classificação de seleção. Em seguida, inspecionamos o desempenho da classificação de seleção com entrada de transtorno de ordem. Winnetou em tem extensão teórica com o método estático para criar aumento incremental. Como assumimos o desempenho é ligeiramente melhor com entrada classificada. Que tal o pior caso? Primeiro, precisamos de uma corrida iniciada em ordem inversa. Vamos adicionar outro método à nossa extensão, que gera rio ordenado ou raça. Tudo bem, vamos fazer nossos testes de desempenho como esperado. Os tempos de execução fora da seleção tipo de pior ao usar recompensas classificadas aumento. Uma grande desvantagem do tipo de seleção é que ele é insensível à entrada. Demora quase tanto tempo para executar a classificação de seleção em uma taxa que já está em ordem, como para uma matriz ordenada aleatoriamente 39. Classificação de seleção - resumo: a classificação de seleção é definitivamente fácil de entender e implementar, pois depende de loops aninhados. É tempo que a complexidade é quadrática. O tempo de execução da classificação de seleção é principalmente afetado pelo número off comparações realizadas pelo algoritmo. O desempenho fora da classificação de seleção é insensível à entrada. O tempo de execução não vai muito se você tipo de seqüência já ordenada. Que totalmente sofrido. Como uma conclusão. Compreender a classificação de seleção e saber como implementá-la é importante, no entanto, tentar evitá-la no código real. No próximo sono, vou mostrar-lhe outro algoritmo simples, que é muito mais rápido quando a entrada já está parcialmente classificada. 40. Classificação de inserção: nesta palestra, vamos falar sobre o tipo de inserção. A classificação concessional é um algoritmo básico de classificação, que funciona analisando cada elemento e inserindo-o em seu lugar apropriado. Elementos maiores se movem na posição para a direita na classificação social tem complexidade de tempo quadrático . No entanto, o desempenho da classificação de inserção é amplamente afetado pela ordem inicial fora dos elementos na sequência. Na demonstração a seguir, vamos implementar o algoritmo de classificação de inserção em Swift. Vamos visualizar como funciona a classificação de inserção. Então vamos analisar a complexidade do tempo desses algoritmos que trabalhamos em que um experimento interessante foram comparados a eficiência da classificação de inserção com o algoritmo de classificação de seleção que foi apresentado no episódio anterior. Agora vamos mudar para o Código X. A função de classificação de inserção leva um dia de folga em apenas como entrada e retorna cópia sortida fora do ary importação. Clonamos o array de importação. Esta cópia irá conter o resultado sórdido. A função de classificação unsocial usa dois loops. O loop externo progride à medida que processamos a matriz começamos índice um porque o loop interno tem que prejudicar o índice como ele inverte o saberi para trás não que não precisamos validar o tamanho de entrada como fizemos na implementação. Fora da função de seleção Espada. O contador de loop externo começa em um e termina no tamanho de importação. Portanto, matrizes de elemento vazio ou único não serão processadas de qualquer maneira. Para uma matriz ordenada, o número no índice atual deve ser maior do que os anteriores. O loop interno passa para trás através da classificação é saberi e swabs os valores se ele encontrar um número anterior que é maior do que o no índice atual, dado o revendedor resposta um 1 para 430 O outlook porca o elemento que índice um, que é para o loop externo, índice iniciado um porque o loop interno deve atravessar a área para trás. O índice externo também marca a porção sórdida fora da matriz, que neste ponto consiste em apenas um elemento. O loop interno compara o número no índice atual, com os elementos na porção sórdida fora da matriz que estes se compara com um, uma vez que dois é maior do que um. Os números não são trocados. A espada é parte inclui os números um para, eo não-ordenado tem os números 430 O loop externo escolhe o elemento que índice para o qual é quatro. O loop interno compara para com os elementos na parte sórdida quatro não é menor do que dois. Portanto, nenhuma troca de um curso o índice externo é incriminado. O próximo elemento é a rua numérica. O loop interno executa as comparações com a porção sórdida três menor que quatro, então eles são trocados. Três não é menor que dois, então eles não são mais trocas. Não temos 1234 na parte sórdida, o outro índice. Porque da última vez e da parte não ordenada fora da matriz visto zero, é mais do que todos os números na porção sórdida que ele é repetido. Esta caminhada com cada item da espada é Saberi. A parte não ordenada está vazia, então agora temos todos os elementos em ordem. A classificação de inserção usa dois loops aninhados. Portanto, o pior momento. Complexidade é quadrática. No entanto. É muito mais desempenho do que o tipo de seleção. Se o Imperatori inclui sequências já ordenadas, veremos isso no momento. Ao contrário da classificação de seleção, que é insensível à entrada, os tempos de execução fora do algoritmo de classificação de inserção podem muito consideravelmente dependendo da ordem fora do Imperatori, os melhores casos quando os arrays já classificadas durante cada geração. O próximo elemento da porção não classificada é apenas comparado com o elemento mais direito da subseção sorties fora da área. Nenhuma troca é feita uma vez que os elementos já estão no lugar para a matriz já ordenada, que tem um elemento que o algoritmo irá executar e menos um compara e zero trocas . Em outras palavras, o melhor tempo de execução fora da classificação de inserção é sênior. Os piores casos quando a entrada está na ordem inversa neste caso, cada duração fora do loop interno. medo comparou o elemento atual com todos os elementos da espada é parte. O número de swaps será igual ao número de itens na subseção sórdida, a pior complexidade caso da inserção, sorties e mentes quadradas. E usando a notação maior, descobrimos um termo mais baixo, o que dá um tempo de execução quadrático para o caso médio. Quando cada elemento está a meio caminho em ordem. O número de swaps e comparações é metade em comparação com o pior caso. Isso nos dá e quadrado menos e mais para o qual é também uma complexidade de tempo quadrático para resumir a classificação de inserção executa em tempo linear para matrizes já ou quase classificadas quando a entrada é sofrida ou na ordem inversa, o classificação de inserção que runnin tempo quadrático. Em seguida, vamos medir o desempenho da classificação de inserção e Jack. Como ele varia com base no tamanho de entrada irá gerar três ou elevar um, que tem 10 elementos, um com 100 elementos e um com 1000 elementos, respectivamente. Negócios Running Times Podemos dizer que o algoritmo de classificação inserção aumentando o tempo quadrático . Agora vamos reexecutar nossos testes com matrizes desordenadas de ordem. Os tempos de execução não mudam tão abruptamente com o tamanho da entrada como fizeram com a entrada sofrida . A classificação de inserção é executada em tempo linear, conforme esperado. Finalmente, comparamos o desempenho da classificação de seleção e os algoritmos de classificação de inserção. Primeiro, vou usar o afiado para os Raios. À medida que o tamanho de entrada aumenta, a classificação de inserção executa mais devagar. Os dois algoritmos são supostamente executados em tempo quadrático, mas a seleção ordenar correr rua como mais rápido para 100 números aleatórios e cerca de 20 vezes mais rápido para 1000 elementos. A classificação de inserção geralmente faz menos comparações do que a fonte de seleção No entanto, a classificação de seleção requer menos trocas. Como vimos na palestra sobre a classificação de seleção, o número máximo de swaps é igual ao tamanho de entrada. Em outras palavras, cresce linearmente com a entrada. No pior dos casos, classificação de inserção normalmente realizará trocas de água fora e quadradas. Como gravar a memória do dedo do pé geralmente é significativamente mais lenta do que a leitura, a classificação de seleção pode ter um desempenho melhor do que a classificação de inserção para uma entrada maior. A situação muda drasticamente se executarmos nossos testes com entradas classificadas. A melhor natureza linear caso da classificação Insertion mostra seus benefícios sobre o algoritmo de classificação de seleção , que é insensível à entrada porque as matrizes ou distorcidas as execuções de classificação de inserção é melhor cenário. Não haverá nenhuma correia, e o número de Compares é um menos um. O algoritmo de classificação de inserção é executado em tempo linear, enquanto o algoritmo de classificação de seleção aumentando o tempo quadrático. Em nosso exemplo, isso se traduz em desempenho quase 10 vezes menor em comparação com a classificação de inserção para resumir os tempos de execução para a classificação de inserção. melhor caso é linear para entrada quase ordenada. Casos médios quadráticos para entrada sofrida, e o pior caso também é quadrático para entrada ordenada reversa 41. Ordenar inserção - resumo: Na palestra anterior, analisamos mais de perto o algoritmo de classificação de inserção. É fácil de entender e implementar, e sua pior complexidade de tempo caso é quadrática. No entanto, seu tempo de execução diminui se a entrada contém elementos já classificados. Na melhor das hipóteses, quando a entrada já está ordenada, a classificação de inserção é executada no final, menos um compara onde n é considerado tamanho put. Ao contrário da seleção classifica o tempo de execução, que, como vimos, é insensível à entrada, a classificação de inserção funciona melhor quando o ímpeto parcial ou totalmente ordenado como uma conclusão. Apesar de sua simplicidade, a classificação de inserção pode executar, surpreendentemente, onde com sequências parcialmente ordenadas. Na verdade, até mesmo a Apple depende da classificação de inserção em sua implementação de classificação. Se o intervalo a ser classificado contiver menos de 20 elementos. Fonte aberta dos anos 50 para que você possa verificar a implementação fora da função dolorida no rápido repositório de ajuda 42. Classificação de bolha: Nosso próximo tópico é Barbara Sort. Este algoritmo funciona repetidamente elevando itens adjacentes e trocando sua posição . Se eles estão na ordem errada na demonstração a seguir, vamos implementar o algoritmo de classificação de bolha. Tal como acontece com os outros algoritmos, vamos analisar a complexidade do tempo fora da classificação bolha e visualizar como ele funciona . Então vamos comparar o pensamento bolha, o tipo de inserção e o tipo de seleção de ritmo em termos de eficiência. Muito bem, vamos mudar para o nosso projecto de parque de diversões. A função de classificação de bolhas assume o raio de inteiros como entrada e retorna uma cópia variada fora da matriz de importação. A função repetidamente iterado através da matriz e compara cada par adjacente. Se os números não estiverem na ordem certa, sua posição será trocada. O processo continua impasses até que todas as sequências classificadas. Os valores mais baixos bolham para o início da teoria. A variável SWAT é usada para rastrear se quaisquer trocas foram feitas durante uma passagem. Se nenhuma parada ocorreu durante o passado, isso significa que os valores estão em ordem e nós realmente o loop exterior Dubai. Vamos ver o tipo de bolha em ação. Começamos com a resposta, geramos 14 a 30 na primeira passagem. Os primeiros 2 elementos são verificados uma vez que um é menor que quatro. A ordem deles é mantida. O próximo urso é estrangeiro para porque quatro é maior do que para suas posições são trocadas. Então comparamos quatro e três. Eles estão agora em ordem, então eles são trocados. O menor par nesta passagem é quatro e zero C zero. São mais do que quatro. Sua posição é trocada. Continuamos com a segunda passagem. Os 3 primeiros elementos já estão em ordem. Portanto, o algoritmo não os esfrega. O primeiro par, que requer troca, é encontrado nos dois e três. O último par já está em ordem, então os mantemos na posição atual. O terceiro passado bolhas o valor zero até que quase atinge o início. Fora da lista, no entanto, ainda não está classificado. Então precisamos de outro passe. A força passou as trocas. O primeiro par de números zero está finalmente no início da sequência, o resto dos primeiros ou desordenados. Mas o algoritmo não está ciente disso, então o algoritmo executa outra passagem. O quinto e último passado não encontra nenhum par que precise ser trocado. Agora que entendemos o funcionamento interno do algoritmo de classificação de bolha, vamos analisar sua complexidade de tempo. Se a entrada já estiver classificada, a classificação da bolha precisa de apenas um passado, que executa e menos um compara o que os elementos que permanecem no lugar para que o número de swaps seja zero. Isso significa que o tempo de execução fora da classificação da bolha depende apenas do tamanho da entrada. Quando as sequências que desordenado. Em outras palavras, a melhor complexidade de tempo fora da classificação de bolha é linear. Os piores casos em que a matriz é invertida para fez ou um itens na sequência do algoritmo, Irã e passa em ordem. Durante cada melhor, nossa função executa e menos uma comparações. Isto significa que n vezes n menos um compara para a sequência de ordem inversa. O número de swaps será um menos um na primeira passagem, en menos dois na segunda passagem, e assim por diante até que a última troca seja feita no penúltimo melhor. O número total de swaps é um menos uma vezes e mais para o pior caso tempo de execução do nosso tipo bolha. Implementação é a soma de dois swaps e compara. Esta é claramente uma ordem fora e complexidade de tempo quadrado. A complexidade média do tempo fora da bolha Pensamento também é quadrática para resumir, a classificação da bolha tem um tempo de execução linear para transtorno da ordem, a corrida e corridas. Em ordem de uma média quadrada e pior complexidade de tempo, esses tempos de execução podem parecer semelhantes às complexidades de tempo do algoritmo de classificação de inserção . No entanto, o tipo de bolha precisa consideravelmente mais swaps do que a espada de inserção. O maior número de trocas resulta em desempenho mais lento. Portanto, a classificação de inserção executa consideravelmente melhor do que a classificação de bolha devido ao seu baixo desempenho. O tipo de bolha quase nunca é usado em software real, entanto, porque é fácil de entender e implementar. O algoritmo de classificação de bolhas é frequentemente usado em materiais introdutórios de ciência da computação. Agora vamos executar algumas medidas de desempenho. Comparamos a classificação de bolha com a classificação de inserção e o algoritmo de classificação de seleção para 10 itens. Não há diferença notável entre os três algoritmos. O algoritmo de pensamento bolha começa a mostrar sua fraqueza ao classificar 100 números aleatórios. Seu desempenho fica pior como o tamanho de entrada loucos 43. Classificação de bolha - resumo: Baba buscado é o terceiro algoritmo de classificação que falamos. Embora seja fácil de implementar, ele tem o pior desempenho entre os algoritmos básicos de classificação. O alto número de swaps tem que culpar o baixo desempenho do tipo bolha. Embora pudéssemos otimizar ligeiramente nossa implementação de classificação de bolha existente, a classificação de inserção vai superar até mesmo a versão otimizada para entrada maior. Como conclusão, você deve evitar Barbara classificação de produção chamado Use Insertion sort. Se você precisa de uma solução simples, mas aceitável. Nesta seção, analisamos alguns dos algoritmos básicos de classificação. Estudá-los é definitivamente vale a pena o esforço para aprofundar nosso conhecimento em algoritmos , no entanto, logo ficaram paralisados, classificando algoritmos que podem correr muito mais rápido do que qualquer fora dos algoritmos elementares que começamos até agora na próxima parte. Vamos examinar os algoritmos mais avançados, mais ordenados e de classificação rápida. Vejo você na próxima seção 44. Seção 8: classificação avançada: nesta seção, vamos estudar algoritmos de classificação muito amplamente utilizados, meu tipo e tipo rápido. Esses algoritmos são desempenho e podem ser realmente usados na produção, chamado muito pensamento e classificação rápida, incluindo em várias bibliotecas e frameworks. Minha espécie funciona dividindo a sequência para ser classificada em duas metades. Então ele serra os que têm e finalmente combina os resultados. A classificação adicional é realizada pela fusão dos Sabri. O algoritmo de classificação rápida usa uma abordagem de divisão e conquista como a fonte de março. A diferença é que o resultado Sabri é nossa ordem, a ordem e como para o mais tipo, a classificação adicional não é necessária pela fusão das peças. Tudo bem, vamos começar com o mais amável. 45. Classificar mesclar: Ok, então vamos falar sobre o tipo mais como você verá em um segundo. Este é um algoritmo que funciona dividindo a matriz em reboque. Metades. Ele continua, dividindo a metade até chegarmos às sub-listas de elemento único. Essas matrizes de um elemento são então classificadas e mescladas. Como resultado, teremos dois elementos. Sujeitos que são ordenados. A classificação, emergente da sub-lista continua. Finalmente, há apenas uma lista. Adivinha o que será esta lista. O resultado sórdido. Que tal implementar a maioria iria concordá-los a partir do zero Na demonstração a seguir, eu vou mostrar-lhe uma implementação de cima para baixo, mais tipo. Mas primeiro, vamos visualizar como funciona. Vou guiá-lo através de um exemplo de ordenar Honore usando mais tipo. Primeiro, dividimos a matriz em duas partes. O início tem oito elementos, então o cuspe indexa quatro. Temos que sublistas, cada uma com quatro elementos. Tudo bem, vamos continuar com a divisão. Depois de dividir a metade esquerda, chegamos a sub-listas, cada uma com dois elementos. Em seguida, dividimos estes dois. Não podemos falar mais do lado esquerdo. Desde agora temos apenas uma matriz de elementos. Então agora vem o rosto de separação e fusão. Após duas etapas, os elementos da metade esquerda são ordenados. Eu sigo os mesmos passos para a metade direita uma rua do que mais duas divisões nas sub-listas de dois elementos, e nós temos o elementar um. Em seguida, As sublinhas de elemento único são classificadas e combinadas até que a metade direita também seja classificada. O que vem a seguir? Só resta um passo. Durante este último passo, os dois pensaram que era meio blindado e sórdido. E lá vai você. O resultado é a ordem Ray. Agora que você sabe como funciona, vamos implementar este algoritmo incrível. Então ele tem a função mais ordenada. Tem uma assinatura simples. O argumento de entrada é a matriz de Inter apenas para ser classificada. A função retorna e ray off, ordenado em apenas bem pelo menos dias atrás. Não faz sentido classificar Honore, que tem um elemento. Os deuses estado um mudou o tamanho fora da importação a cada se ele tem menos de dois elementos, a função simplesmente retorna a entrada. Em seguida, encontramos o índice de divisão que precisamos dividir a direita no meio. Portanto, o índice é calculado como a contagem de entrada sobre dois Como você provavelmente notou, vamos a função Mursal de si mesmo. Este registro asiático é usado para acelerar a metade até que uma ou ambas as casas têm apenas um elemento. Em seguida, o algoritmo estrelou o tipo de fase muito. A primeira função auxiliar compara os itens da sub-lista esquerda e direita. O valor menor é anexado ao ário sórdido. Se o Ray original tem um número ímpar de elementos, não podemos cuspir exatamente em duas metades. É por isso que precisamos dos últimos cheques. Esta etapa final garante que o último elemento do resumo da esquerda ou da direita seja adicionado à lista classificada. Finalmente, menos que o recém-implementar é mais função de classificação. O algoritmo mais ordenado é um pouco mais desafiador do que os básicos que cobrimos até agora . Precaução também não é fácil . Sugiro que você dê uma olhada no projeto do playground, execute-o algumas vezes e tente entender essa lógica. Além disso, revisite a parte em que visualizo como a maioria dos tipos funciona. Infelizmente, o playground não vem com o sacana, mas não se esqueça que você pode imprimir os passos e os valores para o conselho. Sinta-se livre para qualquer pesquisa ou impressão de declarações no código onde você precisar de mais clareza 46. Classificação de mesclagem - resumo: Até agora, falamos sobre três tipos de seleção de algoritmo de classificação básico e mais avançado, inserção,classificação inserção, de baba sort e mais dolorido. O músculo é o mais eficiente entre eles. Tem uma complexidade logarítmica pior e média de tempo. O mais tipo usa uma técnica de divisão e conquista. É por favor o original Ray Recursive Lee em sub-listas menores. Então, no tipo de fase de merchandismo, diz respeito ao resultado ordenado mais classificar melhor do mundo com entradas maiores. Se você precisa classificar pequenas matrizes, digamos menos de 20 elementos, classificação insurgente pode ter um melhor desempenho devido à sua simplesmente cidade. Então, o que vem a seguir? Na próxima palestra, vamos dar uma olhada mais de perto no algoritmo de classificação muito popular e também muito rápido , o tipo rápido. 47. Classificação rápida: classificação rápida é provavelmente o mais amplamente foi algoritmo de classificação é popularmente está relacionado ao seu desempenho. Além disso, não é muito difícil de implementar, e funciona bem com muitos tipos de entrada diferentes. No entanto, a abordagem é diferente. Ao contrário da maioria dos tipos, a classificação final dos elementos acontece antes da fase da mercadoria. Logo eu mostrarei como implementar uma rápida classificação rápida. Mas primeiro, vamos visualizar como esse algoritmo funciona. Então aqui está a nossa resposta. Jittery. Primeiro, precisamos escolher um pivô. O algoritmo usa disputa para dividir seu direito em três partes uma lista com todos os elementos que são menores do que as pessoas, um com os elementos que são iguais às pessoas. E como você deve ter adivinhado uma vez disso, isso contém todos os elementos que são maiores do que as pessoas. Cuspir a matriz em torno das pessoas é pego particionando. O particionamento continua até que não haja mais sequências que exigem classificação. Agora vamos voltar ao nosso exemplo. Nós ampliamos o elemento que o índice para o pivô S. Os três sub-bagas resultantes contêm todos os números que são menores do que três igual a três e maior do que três, respectivamente. Em seguida, dividimos a esquerda mais capaz um espírito. Escolhemos o item no índice um. A sub-lista resultante continha o número 01 e dois para. Como não há números maiores do que estabelecer que deve conter, os números maiores estão vazios. Novamente. Escolhemos um povo e aceleramos o próximo resumo. Você começa a um aumento com apenas um elemento. Agora o processo. A sub-lista mais direita, que contém os elementos que são maiores do que as primeiras pessoas que escolhemos. Seis. Um espírito que nos dá os seguintes Sabri em Sudbury vazia para elementos menores que as pessoas. Um elemento Saberi para elementos iguais às pessoas e um elemento metrô para elementos maiores do que as pessoas. Terminamos com a fase de particionamento. Ao mesclar as sub-listas de terminação, obtemos o resultado sórdido. Tudo bem. Agora, vamos implementar a função de classificação rápida. Esta variante é a implementação mais simples possível. O povo é o elemento do meio da área para petição. Contamos com a função de filtro. A função de início rápido causar-se recursivo Lee, até que todos estabelecidos contêm um elemento ou itens iguais. Finalmente, as sublocações são combinadas. Em Swift. Você pode simplesmente usar o operador de anúncios. Tokcan, Cara, aumento da OTAN Vamos fazer um teste rápido. O resultado sórdido é mostrado no console. Por que esse código é muito simples. Definitivamente não é uma implementação de classificação rápida pronta para produção. Em vez de implementar um esquema de particionamento, contamos com a função de biblioteca de filtros. Isso produz um código muito simples e compacto. No entanto, em termos de desempenho, esta não é definitivamente a melhor escolha. Muitas melhorias foram feitas no algoritmo de classificação rápida original, que foi inventado há quase 60 anos. Encontrar as pessoas ideais e melhores esquemas de particionamento pode melhorar ainda mais a eficiência deste algoritmo inteligente. Uma maneira simples de melhorar o desempenho da classificação rápida é alternar para uma asserção, classificar para arrays menores. Mesmo a Apple usa o distrito na implementação fora da função de classificação rápida. 48. Quicksort - Resumo: Vamos recapitular rapidamente o que aprendemos na palestra anterior. Os gregos. O que é provável que seja executado mais rápido do que qualquer outro algoritmo de classificação de baía de comparação. Na maioria dos casos, esse algoritmo usa a estratégia de divisão e conquista para particionar. A matriz então viu os Sabri de forma independente. A Espada Rápida foi inventada em 1960. Está sendo consistentemente estudado e refinado ao longo do tempo. Mais difícil. O inventor do algoritmo Dextre, Lamu, Toe e outros têm trabalhado na melhoria da eficiência do tipo rápido. Esquemas de particionamento ainda mais inteligentes e encontrar as pessoas ideais podem fazer uma grande diferença. Com isso, terminamos com os algoritmos de classificação. Agora, você provavelmente sabe muito mais sobre algoritmos do que quando começou a pontuação. Mas espere, tem mais. Vejo você na próxima seção. 49. Seção 9: pensamentos finais e recursos úteis: Então você chegou ao fim deste curso. Parabéns. Você aprendeu muito sobre algoritmos e entende seus benefícios. Em caso de dúvida, sinta-se livre para revisitar as palestras no tribunal de seção. O poder de constantes de algoritmos como complexidade de tempo linear ou quadrático não vai fazer você levantar suas sobrancelhas mais. O capítulo sobre a notação Bigelow esclareceu algumas das complexidades de tempo mais comuns por um código rápido. Exemplos sem nos detalhes de três algoritmos de classificação básicos populares e avançados, incluindo a classificação rápida extremamente difundida. Até agora, você provavelmente é capaz de explicar um implemento de algoritmo de classificação a partir do zero. Agora você pode querer aprofundar seu conhecimento ainda mais. Então, o que vem a seguir? Eu dou-lhe algum recurso on-line útil é que irá ajudá-lo a afiar a sua capacidade de acordo e resolução de problemas esquiadores, um grande recurso para ambos os desenvolvedores e recrutadores. Habilidade tem um monte de citações exercícios e desafios. Para testar seu conhecimento, o site fornece um editor e compilador on-line e suporta uma série de linguagens de programação diferentes , incluindo Swift três. Você pode fornecer dados de teste personalizados e executar várias execuções de teste antes de enviar sua solução . A solução é avaliada quanto à correção. Cenários de caso Etch e complexidade de tempo também. Você pode não atingir a pontuação mais alta, mesmo que sua solução forneça os resultados esperados. Se é desempenho lento ou justo, algum caso extremo etch uma abordagem algorítmica é definitivamente necessária para resolver a maioria dos exercícios deste lado. Heck, Arinc Hecker Rank oferece um monte de tutoriais e desafios para Projeto. Oiler é uma coleção de problemas desafiadores de metanfetamina e programação de computador. Você deve continuar trabalhando em melhorar seus problemas algorítmicos resolvendo esquiadores. Você terá que praticar muito para tornar o pensamento algorítmico um hábito. Em vez de pular para implementar uma solução ingênua e lenta. Você acabará por encontrar-se analisando o problema. E considerando vários aspectos, como pior caso, tempo médio de Black City e considerações de memória, você não só vai resolver os problemas, mas você será capaz de fornecer elegante, eficiente e confiável a longo prazo soluções. Eu adoraria ouvir de você. Sinta-se à vontade para me enviar uma mensagem, e se você achou este curso útil, por favor deixe uma melhor classificação do espectador. Obrigado