Melhor resposta
Não há resposta para isso.
Vamos encontrar a resposta para esta declaração de problema:
Q. Como descobrir se algum algoritmo tem um desempenho melhor?
A. Formas mais comuns de comparar algoritmos:
1) Complexidade do tempo
2) Complexidade do espaço
3) Qualidade da solução (pode não ser aplicável se se propõe a resolver exatamente um problema). Este pode ser um fator enorme se estamos falando de algoritmos de aproximação.
4) Facilidade de implementação / adaptação do algoritmo. Alguns algoritmos podem ter muita sobrecarga para serem implementados corretamente. Às vezes, há algoritmos mais adequados para sua aplicação. Por exemplo, em computação paralela, a maioria achará Bellman-Ford mais útil do que o algoritmo de Dijkstra devido à maneira como Bellman-Ford funciona.
No entanto, o tempo e a complexidade não são * sempre * o recurso desejável para maximizar; Vou fornecer dois exemplos.
Um é “estabilidade numérica” , um recurso de algoritmos em álgebra linear e em equações diferenciais. Vamos gastar mais tempo algorítmico e mais complexidade algorítmica em algoritmos que são mais estáveis numericamente. Em álgebra linear, a instabilidade é geralmente causada quando um algoritmo encontra números muito próximos de zero ou infinito ou ambos, porque a representação finita da resolução de números pode ser perdida. Em geral, isso causa números ligeiramente diferentes, apenas alguns épsilon diferentes uns dos outros (onde épsilon é o menor número que pode ser adicionado a um, em uma máquina, e obter um resultado! = 1), para produzir grandes diferenças em a resposta. Assim, por exemplo, gastamos muito tempo e complexidade de espaço “girando” na fatoração LU para obter um algoritmo estável; sem girar LU não é estável. Da mesma forma, temos algoritmos que não fazem nada além de matrizes de “condição” a fim de evitar instabilidade.
Um segundo exemplo é “robustez” em seu sentido técnico estatístico. Robustez significa uma medida ou algoritmo que * não * é sensível a outliers. Então, por exemplo, quando eu ajusto uma linha de mínimos quadrados a um conjunto de pontos, a linha pode ser fortemente distorcida por um único valor extremamente grande. Mesmo se eu tiver 99 pares de números que formem uma linha perfeita de 45 graus, se eu adicionar um único par atípico para o qual o valor de Y é cem vezes o que “deveria” ser para cair na mesma linha, a linha ajustada será severamente desviado da linha de 45 graus. O algoritmo “desistirá” do ajuste perfeito para 99 pontos a fim de representar melhor o ponto discrepante. Isso * não * é robusto.
Uma abordagem de mínimos quadrados robusta é, em vez de encontrar a linha que minimiza a soma dos erros quadrados criados usando essa linha, encontrar a linha que minimiza a * mediana * de os erros quadrados criados usando essa linha. No exemplo, essa linha é a linha de 45 graus e a mediana dos erros quadrados é zero, e o ponto outlier (e de fato até 98 outliers mais loucos) seria completamente ignorado. A linha de 45 graus seria encontrada.
Existem algoritmos robustos semelhantes para ajustar curvas estatísticas, encontrar formas, etc. No entanto, eles são caros em tempo, às vezes severamente caros. Mas o custo de tempo vale a pena porque estatísticas robustas são efetivamente imunes a “ruídos” nos sinais, onde as abordagens de erro quadrático mínimo não são. O mundo real está cheio de ruído e outliers, alguns deles causados por erro humano ou da máquina, em particular em imagens pixeladas ou som amostrado. Em tais circunstâncias, um algoritmo robusto e mais caro pode encontrar sinais em um ambiente barulhento, onde algoritmos mais rápidos produzem respostas tão corrompidas pelo ruído que são inúteis ou mesmo perigosos se aceitos.
Em alguns casos, o tempo e a complexidade do espaço não são tão importantes quanto encontrar uma resposta mais provável para modelar o sinal real apesar do ruído e degradação do sinal.
Resposta
Algoritmos originados na matemática como “receitas” para realizar computação baseada em função, que pode ser seguida mecanicamente. Na visão de mundo matemática baseada em funções, todas as entradas devem ser especificadas no início do cálculo, que prossegue em uma caixa fechada. A noção de um algoritmo é inerentemente informal, uma vez que uma descrição algorítmica não é restrita a qualquer linguagem ou formalismo único.
Talvez o exemplo mais antigo seja o algoritmo de Euclides para encontrar divisores comuns. Algoritmos capturam o que significa para um cálculo ser “eficaz”. Como as fórmulas matemáticas, os algoritmos nos dizem como calcular um valor; ao contrário deles, os algoritmos podem envolver o que agora chamamos de loops ou ramos.
Função do algoritmo: Dado algum valor de entrada finito x, um algoritmo descreve as etapas para transformá-lo efetivamente em um valor de saída y, onde y é f (x) para alguma função recursiva f.
Os algoritmos foram adotados pelos primeiros cientistas da computação na década de 1950, que fizeram a conexão entre algoritmos e máquinas de Turing (TMs, um modelo formal de computação datado de 1936), igualando sua expressividade.
O famoso e influente livro de Knuth, “The Art of Computer Programming, Vol. 1”, no final dos anos 1960, popularizou a centralidade dos algoritmos na ciência da computação. Em sua definição de algoritmos, Knuth foi consistente com os fundamentos baseados em funções matemáticas da teoria da computação. “Existem muitas outras maneiras essencialmente equivalentes de formular o conceito de um método computacional eficaz (por exemplo, usando TMs).”
Knuth especificou explicitamente que os algoritmos são fechados; nenhuma nova entrada é aceita uma vez que o cálculo tenha começado: “Um algoritmo tem zero ou mais entradas, ou seja, quantidades que são fornecidas a ele inicialmente antes do algoritmo começar.” Ele distinguiu algoritmos de computação arbitrária que pode envolver E / S. Um exemplo que ele deu de um problema que não é algorítmico é a seguinte instrução de uma receita: “jogue levemente até que a mistura esteja quebradiça”. Este problema não é algorítmico porque é impossível para um computador saber por quanto tempo a mistura; isso pode depender de condições externas que mudam dinamicamente, como umidade, que não podem ser previstas com certeza com antecedência.
Embora não haja acordo sobre a noção exata de algoritmos, a discussão de Knuth sobre algoritmos permanece definitiva.
A primeira linguagem de programação de alto nível desenvolvida expressamente para especificar algoritmos foi ALGOL (ALGOrithmic Language). Introduzido no final dos anos 50 e aprimorado na década de 1960, ele serviu como um padrão para a publicação de algoritmos. Fiel à conceituação de algoritmos baseada em função, o ALGOL não forneceu nenhuma construção para entrada e saída, considerando essas operações fora da preocupação dos algoritmos. (Não surpreendentemente, essa ausência impediu a adoção do ALGOL pela indústria para aplicações comerciais.)
A década de 1960 viu uma proliferação de programas de graduação em ciência da computação (CS). De acordo com a Association for Computing Machinery (ACM), o número de programas de CS nos EUA aumentou de 11 em 1964 para 92 em 1968. Esse aumento foi acompanhado por uma intensa atividade no sentido de estabelecer a legitimidade dessa nova disciplina aos olhos do acadêmico comunidade. ACM desempenhou um papel central nesta atividade. Em 1965, ele enunciou a justificativa e a descrição da ciência da computação como uma disciplina, que serviu de base para suas recomendações de 1968 para programas de ciência da computação de graduação.
A descrição da ciência da ciência da ACM identificou a transformação efetiva da informação como uma preocupação central: “ A ciência da computação se preocupa com a informação da mesma forma que a física se preocupa com a energia … O cientista da computação está interessado em descobrir os meios pragmáticos pelos quais a informação pode ser transformada ”. Essa descrição coloca os algoritmos no centro da Ciência da Computação, uma vez que são as “receitas” para realizar essas transformações eficazes de entradas em saídas. Na verdade, ACM tornou esse foco em algoritmos explícito na próxima frase de seu relatório:
“Este interesse leva à investigação de maneiras eficazes de representar informações, algoritmos eficazes para transformar informações, linguagens eficazes para expressar algoritmos … e maneiras eficazes de realizá-los a um custo razoável. ”
Ter uma preocupação algorítmica central, análoga à preocupação com a energia na física, ajudou a estabelecer a ciência da computação como uma disciplina acadêmica legítima no mesmo nível física. Os algoritmos permaneceram centrais para a ciência da computação até hoje.
A coexistência das abordagens informal (baseada em algoritmo) e formal (baseada na TM) para definir problemas solucionáveis persiste até hoje e pode ser encontrada em todos os livros modernos sobre algoritmos ou computabilidade. Isso tem se mostrado muito conveniente para cientistas da computação, ao nos permitir descrever a computação algorítmica informalmente usando “pseudocódigo”, com o conhecimento de que uma Máquina de Turing equivalente pode ser construída.
– Um problema é solucionável se puder ser especificado por um algoritmo. – Um problema pode ser resolvido se existir uma Máquina de Turing para ele.
A decisão dos teóricos e educadores de colocar algoritmos no centro da Ciência da Computação foi claramente refletida nos primeiros livros didáticos de graduação. No entanto, não havia uma definição padrão explícita de um algoritmo e vários livros optaram por definir esse termo de maneira diferente. Embora alguns livros didáticos, como o de Knuth, tenham o cuidado de restringir explicitamente os algoritmos àqueles que calculam funções e, portanto, são equivalentes às máquinas de Turing, a maioria dos livros de teoria deixou essa restrição implícita, mas não declarada.
Um exemplo inicial é um livro didático de Hopcroft e Ullman de 1969, cujas edições posteriores são utilizadas até hoje: “Um procedimento é uma sequência finita de instruções que podem ser executadas mecanicamente, como um programa de computador …Um procedimento que sempre termina é chamado de algoritmo. ”
Esta descrição de um algoritmo não exclui explicitamente a computação não funcional, como preparar comida. No entanto, seus exemplos de vários problemas deixam claro que eles consideraram apenas a computação baseada em funções. Na verdade, eles usaram ALGOL para seus exemplos, que nem mesmo oferecia nenhuma construção para entrada e saída.
Desde o final dos anos 60, as linguagens de programação de alto nível usadas na prática e ensinadas em programas de CS não eram mais limitado pelas restrições algorítmicas do ALGOL inicial. Você poderia escrever programas que interagissem com seu ambiente de maneira contínua durante a computação, como sistemas operacionais, interfaces gráficas de usuário ou veículos automáticos e outros robôs.
Em resposta, livros de programação contemporâneos, como Rice e Rice (1969) ampliou explicitamente a noção de algoritmos para incluir problemas não funcionais. Essa abordagem, refletindo a centralidade dos algoritmos sem restringi-los ao cálculo de funções, tornou-se típica de livros didáticos não teóricos. O assunto desses livros é metodologia de programação, em vez de teoria da computação, e os princípios matemáticos que sustentam nossos modelos de computação foram deixados de lado por uma questão de praticidade.
Superficialmente, a definição de um algoritmo em Rice and Rice e outros livros semelhantes não é diferente de Hopcroft e Ullman: “Um algoritmo é uma receita, um conjunto de instruções ou as especificações de um processo para fazer algo. Esse algo geralmente resolve algum tipo de problema. ” No entanto, seus exemplos de problemas computáveis não são mais baseados em funções, admitindo apenas o tipo de cálculo que Knuth rejeitou. Dois desses exemplos, que supostamente podem ser resolvidos por um algoritmo, são fazer vodca de batata e encher uma vala com areia; Knuth teria rejeitado os dois.
Esses livros não faziam alegações de equivalência TM para seus “algoritmos”. No entanto, os alunos não foram informados de que esta noção de algoritmos é diferente da de Knuth, e que o conjunto de problemas considerados computáveis foi, portanto, ampliado. Ao emparelhar uma conceituação mais ampla e prática de algoritmos (e, portanto, de problemas computáveis) com teorias que afirmam que problemas muito computáveis podem ser computados por TMs, o currículo de ciência da computação focado em algoritmos deixou os alunos com a impressão errônea de que este conjunto mais amplo de problemas poderia também pode ser resolvido por TMs.
Embora os cientistas da computação práticos há muito tenham seguido o exemplo de Rice e Rice e ampliado o conceito de algoritmos para além da computação de funções, a ciência da computação teórica manteve a visão de mundo matemática que enquadra computação como baseada em função, e delimita nossa noção de um problema computacional de acordo. Isso é verdade pelo menos no nível de graduação. O resultado é uma dicotomia, onde a comunidade da ciência da computação pensa em algoritmos como sinônimos da noção geral de computação (“o que os computadores fazem”), mas ao mesmo tempo como equivalentes a máquinas de Turing.
Eu pensei Tive que escrever essa longa resposta, para conscientizar as pessoas dessa dicotomia. Como disse no início, a noção de algoritmo é informal. Podemos pensar nisso como equivalente à computação de funções (ou máquinas de Turing) ou podemos pensar nisso como qualquer coisa para a qual você possa escrever um programa, incluindo programas interativos em tempo real, como sistemas operacionais ou carros automáticos. Mas as duas definições não são equivalentes, apesar da confusão comum em contrário.