Em matemática e ciência da computação, um algoritmo AL-gə-ridh-əm é uma especificação inequívoca de como resolver uma classe de problemas. Algoritmos podem executar tarefas de cálculo, processamento de dados e raciocínio automatizado.

Como um método eficaz, um algoritmo pode ser expresso dentro de uma quantidade finita de espaço e tempo e em uma linguagem formal bem definida para o cálculo de uma função. Partindo de um estado inicial e de uma entrada inicial (talvez vazia), as instruções descrevem uma computação que, quando executada, passa por um número finito de estados sucessivos bem definidos, produzindo eventualmente “saída” e terminando em um estado final final. A transição de um estado para o outro não é necessariamente determinista; alguns algoritmos, conhecidos como algoritmos aleatórios, incorporam entrada aleatória.

O conceito de algoritmo existe há séculos e o uso do conceito pode ser atribuído a matemáticos gregos, por exemplo, a peneira de Eratóstenes e o algoritmo de Euclides; o termo algoritmo em si deriva do matemático do século IX, Muhammad ibn Mūsā al’Khwārizmī, latinizado “Algoritmi”. Uma formalização parcial do que se tornaria a noção moderna de algoritmo começou com tentativas de resolver o Entscheidungsproblem (o “problema de decisão”) proposto por David Hilbert em 1928. Formalizações subseqüentes foram enquadradas como tentativas de definir “calculabilidade efetiva” ou “método efetivo”. ; Essas formalizações incluíam as funções recursivas de Gödel-Herbrand-Kleene de 1930, 1934 e 1935, lambda calculus de Alonzo Church de 1936, Emil Post’s Formulation 1 de 1936 e as máquinas de Turing de Alan Turing de 1936-7 e 1939.

Etimologia
A palavra “algoritmo” tem suas raízes na latinização do nome de Muhammad ibn Musa al-Khwarizmi em um primeiro passo para o algorismus. Al-Khwārizmī (persa: خوارزمی, c. 780–850) foi um matemático, astrônomo, geógrafo e estudioso persa na Casa da Sabedoria em Bagdá, cujo nome significa “o nativo de Khwarezm”, uma região que fazia parte Grande Irã e agora está no Uzbequistão.

Por volta de 825, al-Khwarizmi escreveu um tratado de língua árabe sobre o sistema numeral hindu-árabe, que foi traduzido para o latim durante o século XII sob o título Algoritmi de numero Indorum. Este título significa “Algoritmi no número dos índios”, onde “Algoritmi” era a latização do tradutor do nome de Al-Khwarizmi. Al-Khwarizmi foi o matemático mais lido na Europa no final da Idade Média, principalmente através de outro de seus livros, a Álgebra. No latim medieval tardio, o algorismus, o “algorismo” inglês, a corrupção de seu nome, significava simplesmente o “sistema numérico decimal”. No século XV, sob a influência da palavra grega ἀριθμός ‘number’ (cf. ‘aritmética’), a palavra latina foi alterada para algorítmo, e o termo inglês correspondente ‘algoritmo’ é primeiro atestado no século XVII; o sentido moderno foi introduzido no século XIX.

Em inglês, foi usado pela primeira vez por volta de 1230 e depois por Chaucer em 1391. O inglês adotou o termo francês, mas foi somente no final do século XIX que o “algoritmo” assumiu o significado que tem no inglês moderno.

Outro uso precoce da palavra é de 1240, em um manual intitulado Carmen de Algorismo composto por Alexandre de Villedieu. Começa assim:

Haec algorismus ars praesens dicitur, em qua / Talibus Indorum fruimur bis quinque figuris.

que se traduz como:

Algorismo é a arte pela qual atualmente usamos as figuras indianas, que são duas vezes cinco.

O poema tem algumas centenas de linhas e resume a arte de calcular com o novo estilo de dados indianos, ou Talibus Indorum, ou numerais hindus.

Definição informal
Para uma apresentação detalhada dos vários pontos de vista sobre a definição de “algoritmo”, consulte Caracterizações de algoritmo.
Uma definição informal poderia ser “um conjunto de regras que define com precisão uma seqüência de operações”. o que inclui todos os programas de computador, incluindo programas que não realizam cálculos numéricos. Geralmente, um programa é apenas um algoritmo se parar eventualmente.

Um exemplo prototípico de um algoritmo é o algoritmo euclidiano para determinar o divisor comum máximo de dois inteiros; Um exemplo (existem outros) é descrito pelo fluxograma acima e como exemplo em uma seção posterior.

Boolos, Jeffrey e 1974, 1999, oferecem um significado informal da palavra na seguinte citação:

Nenhum ser humano pode escrever rápido o suficiente, ou longo o suficiente, ou pequeno o suficiente († “menor e menor sem limite … você estaria tentando escrever em moléculas, em átomos, em elétrons”) para listar todos os membros de uma Enumeravelmente infinito definido por escrever seus nomes, um após o outro, em alguma notação. Mas os humanos podem fazer algo igualmente útil, no caso de certos conjuntos infinitos enumeráveis: Eles podem dar instruções explícitas para determinar o enésimo membro do conjunto, para n finito arbitrário. Tais instruções devem ser dadas de forma bastante explícita, de uma forma em que poderiam ser seguidas por uma máquina de computação, ou por um humano que seja capaz de realizar apenas operações muito elementares em símbolos.

Um “conjunto infinito enumerável” é aquele cujos elementos podem ser colocados em correspondência um-para-um com os inteiros. Assim, Boolos e Jeffrey estão dizendo que um algoritmo implica instruções para um processo que “cria” inteiros de saída a partir de um inteiro “entrada” arbitrário ou inteiros que, em teoria, podem ser arbitrariamente grandes. Assim, um algoritmo pode ser uma equação algébrica, como y = m + n – duas “variáveis ​​de entrada” arbitrárias men que produzem uma saída y. Mas as tentativas de vários autores para definir a noção indicam que a palavra implica muito mais do que isso, algo na ordem de (para o exemplo de adição):

Instruções precisas (em linguagem entendida por “o computador”) para um processo rápido, eficiente, “bom” que especifica os “movimentos” do “computador” (máquina ou humano, equipado com as informações e capacidades internas necessárias) para encontrar , decodificar e, em seguida, processar inteiros / símbolos de entrada arbitrária m e n, símbolos + e = … e “efetivamente” produzir, em um tempo “razoável”, saída-inteiro y em um local especificado e em um formato especificado.
O conceito de algoritmo também é usado para definir a noção de decidibilidade. Essa noção é central para explicar como sistemas formais surgem a partir de um pequeno conjunto de axiomas e regras. Na lógica, o tempo que um algoritmo requer para completar não pode ser medido, pois aparentemente não está relacionado com a nossa habitual dimensão física. A partir de tais incertezas, que caracterizam o trabalho em andamento, advém a indisponibilidade de uma definição de algoritmo que atenda ao uso concreto (em algum sentido) e abstrato do termo.

Formalização
Algoritmos são essenciais para o modo como os computadores processam os dados. Muitos programas de computador contêm algoritmos que detalham as instruções específicas que um computador deve executar (em uma ordem específica) para executar uma tarefa específica, como o cálculo dos cheques de pagamento dos funcionários ou a impressão de boletins escolares. Assim, um algoritmo pode ser considerado como qualquer sequência de operações que pode ser simulada por um sistema completo de Turing. Os autores que afirmam esta tese incluem Minsky (1967), Savage (1987) e Gurevich (2000):

Minsky: “Mas nós também manteremos, com Turing … que qualquer procedimento que poderia” naturalmente “ser chamado de efetivo, pode de fato ser realizado por uma máquina (simples). Embora isto possa parecer extremo, os argumentos … em seu favor é difícil de refutar “.

Gurevich: “… o argumento informal de Turing em favor de sua tese justifica uma tese mais forte: todo algoritmo pode ser simulado por uma máquina de Turing … de acordo com Savage [1987], um algoritmo é um processo computacional definido por uma máquina de Turing” .

Normalmente, quando um algoritmo é associado ao processamento de informações, os dados podem ser lidos de uma fonte de entrada, gravados em um dispositivo de saída e armazenados para processamento adicional. Dados armazenados são considerados como parte do estado interno da entidade que executa o algoritmo. Na prática, o estado é armazenado em uma ou mais estruturas de dados.

Para alguns desses processos computacionais, o algoritmo deve ser rigorosamente definido: especificado na forma como se aplica em todas as circunstâncias possíveis que possam surgir. Ou seja, qualquer passo condicional deve ser tratado sistematicamente, caso a caso; os critérios para cada caso devem ser claros (e computáveis).

Como um algoritmo é uma lista precisa de etapas precisas, a ordem de cálculo é sempre crucial para o funcionamento do algoritmo. Geralmente, as instruções são consideradas listadas explicitamente e são descritas como iniciando “de cima” e indo “para baixo”, uma ideia descrita mais formalmente pelo fluxo de controle.

Até agora, essa discussão sobre a formalização de um algoritmo assumiu as premissas da programação imperativa. Esta é a concepção mais comum, e tenta descrever uma tarefa em meios discretos, “mecânicos”. Exclusivo para essa concepção de algoritmos formalizados é a operação de atribuição, configurando o valor de uma variável. Deriva da intuição da “memória” como um bloco de anotações. Existe um exemplo abaixo de tal atribuição.

Para algumas concepções alternativas do que constitui um algoritmo, ver programação funcional e programação lógica.

Expressando Algoritmos
Algoritmos podem ser expressos em muitos tipos de notação, incluindo linguagens naturais, pseudocódigo, fluxogramas, diagramas, linguagens de programação ou tabelas de controle (processadas por intérpretes). Expressões de algoritmos em linguagem natural tendem a ser verbosas e ambíguas e raramente são usadas para algoritmos complexos ou técnicos. Pseudocódigo, fluxogramas, diagramas e tabelas de controle são formas estruturadas de expressar algoritmos que evitam muitas das ambiguidades comuns em enunciados em linguagem natural. As linguagens de programação destinam-se principalmente à expressão de algoritmos em uma forma que pode ser executada por um computador, mas são frequentemente usadas como uma forma de definir ou documentar algoritmos.

Existe uma grande variedade de representações possíveis e pode-se expressar um dado programa de máquina de Turing como uma seqüência de tabelas de máquina (veja mais em máquina de estados finitos, tabela de transição de estados e tabela de controle), como fluxogramas e diagramas (veja mais em diagrama de estado), ou como uma forma de código de máquina rudimentar ou código de montagem chamado “conjuntos de quadruplos” (veja mais na máquina de Turing).

Representações de algoritmos podem ser classificadas em três níveis aceitos da descrição da máquina de Turing:

1 descrição de alto nível
“… prosa para descrever um algoritmo, ignorando os detalhes da implementação. Neste nível, não precisamos mencionar como a máquina gerencia sua fita ou cabeça.”
2 Descrição da implementação
“… prosa usada para definir a maneira como a máquina de Turing usa sua cabeça e a maneira como ela armazena dados em sua fita. Neste nível, não damos detalhes de estados ou função de transição.”
3 Descrição formal
O mais detalhado, o “nível mais baixo”, fornece a “tabela de estados” da máquina de Turing.
Para um exemplo do algoritmo simples “Adicionar m + n” descrito em todos os três níveis, consulte Algoritmo # Exemplos.

Implementação
A maioria dos algoritmos se destina a ser implementada como programas de computador. No entanto, os algoritmos também são implementados por outros meios, como em uma rede neural biológica (por exemplo, o cérebro humano implementando aritmética ou um inseto à procura de alimento), em um circuito elétrico ou em um dispositivo mecânico.

Algoritmos de computador
Em sistemas de computador, um algoritmo é basicamente uma instância de lógica escrita em software por desenvolvedores de software para ser eficaz para o (s) computador (es) “alvo” pretendido (s) produzir saída de dado (talvez nulo) input. Um algoritmo ideal, mesmo rodando em hardware antigo, produziria resultados mais rápidos do que um algoritmo não ótimo (maior complexidade de tempo) para o mesmo propósito, rodando em um hardware mais eficiente; É por isso que algoritmos, como hardware de computador, são considerados tecnologia.

Programas “elegantes” (compactos), programas “bons” (rápidos): A noção de “simplicidade e elegância” aparece informalmente em Knuth e precisamente em Chaitin:

Knuth: “… Queremos bons algoritmos em algum sentido estético vagamente definido. Um critério … é o tempo necessário para executar o algoritmo. Outros critérios são a adaptabilidade do algoritmo aos computadores, sua simplicidade e elegância. , etc ”
Chaitin: “… um programa é ‘elegante’, o que significa que é o menor programa possível para produzir a saída que ele faz”
Chaitin prefacia sua definição com: “Eu mostrarei que você não pode provar que um programa é ‘elegante'” – tal prova resolveria o problema de Halting (ibid).

Algoritmo versus função computável por um algoritmo: Para uma dada função podem existir múltiplos algoritmos. Isso é verdade, mesmo sem expandir o conjunto de instruções disponíveis para o programador. Rogers observa que “é importante distinguir entre a noção de algoritmo, isto é, o procedimento e a noção de função computável por algoritmo, isto é, o mapeamento gerado pelo procedimento. A mesma função pode ter vários algoritmos diferentes”.

Infelizmente, pode haver um compromisso entre bondade (velocidade) e elegância (compacidade) – um programa elegante pode levar mais passos para concluir um cálculo do que um menos elegante. Um exemplo que usa o algoritmo de Euclides aparece abaixo.

Computadores (e computors), modelos de computação: Um computador (ou “computor” humano) é um tipo restrito de máquina, um “dispositivo mecânico discreto determinístico” que segue cegamente suas instruções. Os modelos primitivos de Melzak e Lambek reduziram essa noção a quatro elementos: (i) locais discretos e distinguíveis, (ii) contadores discretos e indistinguíveis (iii) um agente e (iv) uma lista de instruções que são eficazes em relação à capacidade do agente.

Simulação de um algoritmo: linguagem computacional (computor): Knuth aconselha o leitor que “a melhor maneira de aprender um algoritmo é experimentá-lo … imediatamente pegue caneta e papel e trabalhe com um exemplo”. Mas o que dizer de uma simulação ou execução da coisa real? O programador deve traduzir o algoritmo em uma linguagem que o simulador / computador / computor possa efetivamente executar. Stone dá um exemplo disso: ao calcular as raízes de uma equação quadrática, o computor deve saber como obter uma raiz quadrada. Se não, o algoritmo, para ser eficaz, deve fornecer um conjunto de regras para extrair uma raiz quadrada.

Isso significa que o programador deve conhecer uma “linguagem” que seja efetiva em relação ao agente de computação de destino (computador / computador).

Análise algorítmica
É freqüentemente importante saber quanto de um recurso específico (como tempo ou armazenamento) é teoricamente necessário para um determinado algoritmo. Métodos foram desenvolvidos para a análise de algoritmos para obter tais respostas quantitativas (estimativas); por exemplo, o algoritmo de ordenação acima tem um requisito de tempo de O (n), usando a notação grande O com n como o comprimento da lista. Em todos os momentos, o algoritmo precisa apenas se lembrar de dois valores: o maior número encontrado até o momento e sua posição atual na lista de entrada. Portanto, diz-se que tem um requisito de espaço de O (1), se o espaço necessário para armazenar os números de entrada não for contado, ou O (n) se for contado.

Formal versus empírico
A análise e o estudo de algoritmos é uma disciplina da ciência da computação e é praticada abstratamente sem o uso de uma linguagem de programação ou implementação específica. Nesse sentido, a análise de algoritmos se assemelha a outras disciplinas matemáticas, pois concentra-se nas propriedades subjacentes do algoritmo e não nas especificidades de qualquer implementação específica. Normalmente, o pseudocódigo é usado para análise, pois é a representação mais simples e mais geral. No entanto, em última análise, a maioria dos algoritmos são geralmente implementados em plataformas específicas de hardware / software e sua eficiência algorítmica é eventualmente testada usando código real. Para a solução de um problema “one off”, a eficiência de um algoritmo particular pode não ter consequências significativas (a menos que n seja extremamente grande), mas para algoritmos projetados para uso científico interativo, comercial ou de longa vida útil, pode ser crítico. O escalonamento do pequeno n ao grande n frequentemente expõe algoritmos ineficientes que, de outra forma, seriam benignos.

Eficiência de execução
Para ilustrar as possíveis melhorias possíveis mesmo em algoritmos bem estabelecidos, uma recente inovação significativa, relacionada a algoritmos de FFT (usados ​​intensamente no campo do processamento de imagens), pode reduzir o tempo de processamento em até 1.000 vezes para aplicações como imagens médicas. Em geral, as melhorias de velocidade dependem de propriedades especiais do problema, que são muito comuns em aplicações práticas. Acelerações dessa magnitude permitem que dispositivos de computação que fazem uso extensivo do processamento de imagens (como câmeras digitais e equipamentos médicos) consumam menos energia.

Classificação
Existem várias maneiras de classificar algoritmos, cada um com seus próprios méritos.

Por implementação
Uma maneira de classificar algoritmos é por meios de implementação.

Recursão
Um algoritmo recursivo é aquele que invoca (faz referência a) ele mesmo repetidamente até que uma certa condição (também conhecida como condição de terminação) corresponda, o que é um método comum à programação funcional. Os algoritmos iterativos usam construções repetitivas como loops e, às vezes, estruturas de dados adicionais, como pilhas para resolver os problemas dados. Alguns problemas são naturalmente adequados para uma implementação ou outra. Por exemplo, as torres de Hanoi são bem entendidas usando a implementação recursiva. Cada versão recursiva tem uma versão iterativa equivalente (mas possivelmente mais ou menos complexa) e vice-versa.

Lógico
Um algoritmo pode ser visto como dedução lógica controlada. Esta noção pode ser expressa como: Algoritmo = lógica + controle. O componente lógico expressa os axiomas que podem ser usados ​​na computação e o componente de controle determina o modo pelo qual a dedução é aplicada aos axiomas. Esta é a base para o paradigma de programação lógica. Em linguagens de programação lógica pura, o componente de controle é fixo e os algoritmos são especificados fornecendo apenas o componente lógico. O apelo dessa abordagem é a semântica elegante: uma mudança nos axiomas tem uma mudança bem definida no algoritmo.

Serial, paralelo ou distribuído
Algoritmos são geralmente discutidos com a suposição de que os computadores executam uma instrução de um algoritmo por vez. Esses computadores são às vezes chamados de computadores seriais. Um algoritmo projetado para tal ambiente é chamado de algoritmo serial, em oposição a algoritmos paralelos ou algoritmos distribuídos. Os algoritmos paralelos aproveitam as arquiteturas de computador nas quais vários processadores podem trabalhar em um problema ao mesmo tempo, enquanto os algoritmos distribuídos utilizam várias máquinas conectadas a uma rede de computadores. Algoritmos paralelos ou distribuídos dividem o problema em subproblemas mais simétricos ou assimétricos e reúnem os resultados juntos. O consumo de recursos nesses algoritmos não é apenas ciclos de processador em cada processador, mas também a sobrecarga de comunicação entre os processadores. Alguns algoritmos de classificação podem ser paralelizados de forma eficiente, mas sua sobrecarga de comunicação é cara. Os algoritmos iterativos são geralmente paralelizáveis. Alguns problemas não possuem algoritmos paralelos e são chamados de problemas inerentemente em série.

Determinístico ou não determinístico
Algoritmos determinísticos resolvem o problema com a decisão exata em cada passo do algoritmo, enquanto algoritmos não-determinísticos resolvem problemas por meio de adivinhação, embora estimativas típicas sejam feitas com mais precisão através do uso de heurísticas.

Exato ou aproximado
Enquanto muitos algoritmos atingem uma solução exata, os algoritmos de aproximação buscam uma aproximação mais próxima da verdadeira solução. A aproximação pode ser alcançada usando uma estratégia determinística ou aleatória. Esses algoritmos têm valor prático para muitos problemas difíceis. Um dos exemplos de um algoritmo aproximado é o problema da mochila. O problema da mochila é um problema em que há um conjunto de itens fornecidos. O objetivo do problema é empacotar a mochila para obter o valor total máximo. Cada item tem algum peso e algum valor. O peso total que podemos carregar não é mais do que um número fixo X. Portanto, devemos considerar os pesos dos itens, bem como o seu valor.

Algoritmo quântico
Eles correm em um modelo realista de computação quântica. O termo é geralmente usado para aqueles algoritmos que parecem inerentemente quânticos, ou usam alguma característica essencial da computação quântica, como a superposição quântica ou entrelaçamento quântico.

Por paradigma de design
Outra maneira de classificar algoritmos é por sua metodologia ou paradigma de design. Existe um certo número de paradigmas, cada um diferente do outro. Além disso, cada uma dessas categorias inclui muitos tipos diferentes de algoritmos. Alguns paradigmas comuns são:

Força bruta ou busca exaustiva
Este é o método ingênuo de tentar todas as soluções possíveis para ver qual é o melhor.

Dividir e conquistar
Um algoritmo de divisão e conquista reduz repetidamente uma instância de um problema para uma ou mais instâncias menores do mesmo problema (geralmente recursivamente) até que as instâncias sejam pequenas o suficiente para serem resolvidas facilmente. Um exemplo de divisão e conquista é mesclar a classificação. A classificação pode ser feita em cada segmento de dados depois de dividir os dados em segmentos e a classificação de dados inteiros pode ser obtida na fase de conquista, mesclando os segmentos. Uma variante mais simples de dividir e conquistar é chamada de um algoritmo de diminuição e conquista, que resolve um subproblema idêntico e usa a solução desse subproblema para resolver o problema maior. Dividir e conquistar divide o problema em vários subproblemas e, assim, o estágio de conquista é mais complexo do que diminuir e conquistar algoritmos. Um exemplo de algoritmo de diminuição e conquista é o algoritmo de busca binária.

Pesquisa e enumeração
Muitos problemas (como jogar xadrez) podem ser modelados como problemas em gráficos. Um algoritmo de exploração de gráfico especifica regras para mover um gráfico e é útil para tais problemas. Essa categoria também inclui algoritmos de pesquisa, enumeração de ramificação e encadernação e backtracking.
Algoritmo aleatório

Redução de complexidade
Essa técnica envolve a solução de um problema difícil, transformando-o em um problema mais conhecido, para o qual temos (esperamos) algoritmos assintoticamente otimizados. O objetivo é encontrar um algoritmo de redução cuja complexidade não seja dominada pelo algoritmo reduzido resultante. Por exemplo, um algoritmo de seleção para encontrar a mediana em uma lista não classificada envolve primeiro classificar a lista (a parte cara) e depois retirar o elemento do meio na lista classificada (a parte barata). Essa técnica também é conhecida como transformar e conquistar.

Problemas de otimização
Para problemas de otimização, há uma classificação mais específica de algoritmos; um algoritmo para tais problemas pode se enquadrar em uma ou mais das categorias gerais descritas acima, bem como em um dos seguintes:

Programação linear
Ao procurar por soluções ótimas para uma função linear vinculada a restrições lineares de igualdade e desigualdade, as restrições do problema podem ser usadas diretamente na produção de soluções ótimas. Existem algoritmos que podem resolver qualquer problema nesta categoria, como o popular algoritmo simplex. Problemas que podem ser resolvidos com programação linear incluem o problema de fluxo máximo para gráficos direcionados. Se um problema exigir adicionalmente que um ou mais dos desconhecidos devam ser um número inteiro, ele será classificado em programação inteira. Um algoritmo de programação linear pode resolver esse problema se puder ser provado que todas as restrições para valores inteiros são superficiais, ou seja, as soluções satisfazem essas restrições de qualquer maneira. No caso geral, um algoritmo especializado ou um algoritmo que encontra soluções aproximadas é usado, dependendo da dificuldade do problema.
Programaçao dinamica

Quando um problema mostra subestruturas ótimas – ou seja, a solução ótima para um problema pode ser construída de soluções ótimas para subproblemas – e subproblemas sobrepostos, significando que os mesmos subproblemas são usados ​​para resolver várias instâncias de problemas diferentes, uma abordagem mais rápida chamada programação dinâmica evita recomputar soluções que já foram computados. Por exemplo, o algoritmo de Floyd-Warshall, o caminho mais curto para um objetivo de um vértice em um grafo ponderado pode ser encontrado usando o caminho mais curto para o objetivo de todos os vértices adjacentes. A programação dinâmica e a memorização andam juntas. A principal diferença entre programação dinâmica e divisão e conquista é que os subproblemas são mais ou menos independentes em divisão e conquista, enquanto os subproblemas se sobrepõem à programação dinâmica. A diferença entre a programação dinâmica e a recursão direta está no armazenamento em cache ou na memorização de chamadas recursivas. Quando os subproblemas são independentes e não há repetição, a memorização não ajuda; Portanto, a programação dinâmica não é uma solução para todos os problemas complexos. Usando a memorização ou mantendo uma tabela de subproblemas já solucionada, a programação dinâmica reduz a natureza exponencial de muitos problemas à complexidade polinomial.

O método ganancioso
Um algoritmo guloso é semelhante a um algoritmo de programação dinâmica, pois trabalha examinando subestruturas, neste caso, não do problema, mas de uma dada solução. Esses algoritmos começam com alguma solução, que pode ser dada ou construída de alguma forma, e melhorá-la fazendo pequenas modificações. Para alguns problemas, eles podem encontrar a solução ideal, enquanto para outros eles param em locais ótimos, isto é, em soluções que não podem ser melhoradas pelo algoritmo, mas não são ótimas. O uso mais popular de algoritmos gulosos é encontrar a árvore geradora mínima onde é possível encontrar a solução ótima com este método. Huffman Tree, Kruskal, Prim, Sollin são algoritmos gulosos que podem resolver este problema de otimização.

O método heurístico
Em problemas de otimização, os algoritmos heurísticos podem ser usados ​​para encontrar uma solução próxima da solução ótima nos casos em que encontrar a solução ótima é impraticável. Esses algoritmos funcionam aproximando-se cada vez mais da solução ideal à medida que progridem. Em princípio, se for executado por um período infinito, eles encontrarão a solução ideal. Seu mérito é que eles podem encontrar uma solução muito próxima da solução ótima em um tempo relativamente curto. Tais algoritmos incluem pesquisa local, pesquisa de tabu, simulated annealing e algoritmos genéticos. Alguns deles, como o simulated annealing, são algoritmos não determinísticos, enquanto outros, como a tabu search, são determinísticos. Quando um limite do erro da solução não ótima é conhecido, o algoritmo é ainda categorizado como um algoritmo de aproximação.

Por campo de estudo
Cada campo da ciência tem seus próprios problemas e precisa de algoritmos eficientes. Problemas relacionados em um campo são freqüentemente estudados juntos. Algumas classes de exemplo são algoritmos de busca, algoritmos de ordenação, algoritmos de fusão, algoritmos numéricos, algoritmos gráficos, algoritmos de string, algoritmos geométricos computacionais, algoritmos combinatórios, algoritmos médicos, aprendizado de máquina, criptografia, algoritmos de compressão de dados e técnicas de análise.

Os campos tendem a se sobrepor uns aos outros, e os avanços do algoritmo em um campo podem melhorar os de outros campos, às vezes completamente não relacionados. Por exemplo, a programação dinâmica foi inventada para otimizar o consumo de recursos na indústria, mas agora é usada na solução de uma ampla gama de problemas em muitos campos.

Pela complexidade
Algoritmos podem ser classificados pela quantidade de tempo que precisam completar em comparação com o tamanho de entrada:

Tempo constante: se o tempo necessário para o algoritmo é o mesmo, independentemente do tamanho da entrada. Por exemplo, um acesso a um elemento de matriz.
Tempo linear: se o tempo for proporcional ao tamanho da entrada. Por exemplo, a travessia de uma lista.
Tempo logarítmico: se o tempo é uma função logarítmica do tamanho da entrada. Por exemplo, algoritmo de busca binária.
Tempo polinomial: se o tempo é uma potência do tamanho da entrada. Por exemplo, o algoritmo de classificação de bolhas tem complexidade de tempo quadrática.
Tempo exponencial: se o tempo é uma função exponencial do tamanho da entrada. Por exemplo, busca por força bruta.
Alguns problemas podem ter vários algoritmos de complexidade diferente, enquanto outros problemas podem não ter algoritmos ou nenhum algoritmo eficiente conhecido. Existem também mapeamentos de alguns problemas para outros problemas. Devido a isso, verificou-se ser mais adequado para classificar os problemas em si, em vez de os algoritmos em classes de equivalência com base na complexidade dos melhores algoritmos possíveis para eles.

Algoritmos Contínuos
O adjetivo “contínuo” quando aplicado à palavra “algoritmo” pode significar:

Um algoritmo operando em dados que representam quantidades contínuas, mesmo que esses dados sejam representados por aproximações discretas – tais algoritmos são estudados em análise numérica; ou
Um algoritmo na forma de uma equação diferencial que opera continuamente nos dados, sendo executado em um computador analógico.