Há muitas perguntas sobre como analisar o tempo de execução de algoritmos (ver, por exemplo, tempo de execução, análise e algoritmo de análise ). Muitos são semelhantes, por exemplo, aqueles que solicitam uma análise de custos de loops aninhados ou algoritmos de dividir e conquistar, mas a maioria das respostas parece ser feita sob medida.
Por outro lado, as respostas para outra pergunta geral explicam o quadro geral (em particular a análise assintótica) com alguns exemplos, mas não como sujar as mãos.
Existe um método geral estruturado para analisar o custo dos algoritmos? O custo pode ser o tempo de execução (complexidade do tempo) ou alguma outra medida de custo, como o número de comparações executadas, a complexidade do espaço ou qualquer outra coisa.
Isso deveria se tornar uma pergunta de referência que pode ser usada para apontar iniciantes; daí seu escopo mais amplo que o usual. Tome cuidado para fornecer respostas gerais, apresentadas didaticamente, ilustradas por pelo menos um exemplo, mas, no entanto, abrangem muitas situações. Obrigado!
Respostas:
Traduzindo código para matemática
Dada uma semântica operacional (mais ou menos) formal , você pode traduzir o código (pseudo-) de um algoritmo literalmente em uma expressão matemática que fornece o resultado, desde que você possa manipular a expressão em uma forma útil. Isso funciona bem para aditivos medidas custo, tais como o número de comparações, swaps, declarações, acessos à memória, ciclos algumas necessidades máquina abstrata, e assim por diante.
Exemplo: Comparações no Bubblesort
Considere este algoritmo que classifica uma determinada matriz
A
:Digamos que queremos realizar a análise usual do algoritmo de classificação, que é contar o número de comparações de elementos (linha 5). Notamos imediatamente que essa quantidade não depende do conteúdo da matrizn
A
, apenas do seu comprimento . Portanto, podemos traduzir os loops (aninhados) literalmente em somas (aninhadas); a variável de loop se torna a variável de soma e o intervalo é transferido. Nós temos:for
onde é o custo para cada execução da linha 5 (que contamos).1
Exemplo: Swaps no Bubblesort
por o subprograma que consiste em linhas para e por os custos para executar esse subprograma (uma vez).Pi,j Ci,j
i
j
Agora, digamos que queremos contar swaps , é com que frequência é executado. Este é um "bloco básico", que é um subprograma que é sempre executado atomicamente e tem algum custo constante (aqui, ). A contratação de tais blocos é uma simplificação útil que geralmente aplicamos sem pensar ou falar sobre isso.P6,8 1
Com uma tradução semelhante à anterior, chegamos à seguinte fórmula:
Observe que eu uso vez de como parâmetro; em breve veremos o porquê. Eu não adiciono e como parâmetros de já que os custos não dependem deles aqui (no modelo de custo uniforme , que é); em geral, eles apenas podem.A n i j C5,9
Claramente, os custos de dependem do conteúdo de (os valores e , especificamente), portanto, temos que prestar contas disso. Agora enfrentamos um desafio: como "desembrulhamos" ? Bem, podemos deixar explícita a dependência do conteúdo de :P5,9 A C5,9 A
A[j]
A[j+1]
Para qualquer matriz de entrada, esses custos são bem definidos, mas queremos uma declaração mais geral; precisamos fazer suposições mais fortes. Vamos investigar três casos típicos.
O pior caso
Apenas olhando a soma e observando que , podemos encontrar um limite superior trivial para o custo:C5,9(A(i,j))∈{0,1}
Mas isso pode acontecer , ou seja, existe um para esse limite superior ser alcançado? Como se vê, sim: se introduzirmos uma matriz inversamente classificada de elementos distintos em pares, toda iteração deve executar uma troca¹. Portanto, derivamos o número exato de piores casos de trocas de Bubblesort.A
O melhor caso
Por outro lado, há um limite inferior trivial:
Isso também pode acontecer: em uma matriz que já está classificada, o Bubblesort não executa uma única troca.
O caso médio
O pior e o melhor dos casos abrem uma lacuna. Mas qual é o número típico de swaps? Para responder a essa pergunta, precisamos definir o que "típico" significa. Em teoria, não temos motivos para preferir uma entrada a outra e, portanto, geralmente assumimos uma distribuição uniforme entre todas as entradas possíveis, ou seja, todas as entradas são igualmente prováveis. Nós nos restringimos a matrizes com elementos distintos aos pares e, portanto, assumimos o modelo de permutação aleatória .
Em seguida, podemos reescrever nossos custos dessa maneira²:
Agora temos que ir além da simples manipulação de somas. Observando o algoritmo, observamos que toda troca remove exatamente uma inversão em (nós sempre trocamos os vizinhos³). Ou seja, o número de swaps realizadas em é exatamente o número de inversões de . Assim, podemos substituir as duas somas internas e obterA A inv(A) A
Para nossa sorte, o número médio de inversões foi determinado como sendo
qual é o nosso resultado final. Observe que esse é exatamente metade do custo do pior caso.
i = n-1
do loop externo que nunca faz nada não seja executada.O método geral
Vimos no exemplo que temos que traduzir a estrutura de controle em matemática; Vou apresentar um conjunto típico de regras de tradução. Também vimos que o custo de qualquer subprograma pode depender do estado atual , que é (aproximadamente) os valores atuais das variáveis. Como o algoritmo (geralmente) modifica o estado, o método geral é um pouco complicado de anotar. Se você começar a se sentir confuso, sugiro que você volte ao exemplo ou crie o seu.
Denotamos com o estado atual (imagine-o como um conjunto de atribuições de variáveis). Quando executamos um programa iniciando no estado , acabamos no estado (fornecido termina).ψ ψ ψ/P
P
P
Declarações individuais
Dada apenas uma declaraçãoCS(ψ)
S;
, você atribui a ela . Isso normalmente será uma função constante.Expressões
Se você tiver uma expressão
E
da formaE1 ∘ E2
(por exemplo, uma expressão aritmética em que∘
possa haver adição ou multiplicação, adicione custos recursivamente:Observe que
então você pode ter que ser flexível com esta regra.
Seqüência
Dado um programa
P
como sequência de programasQ;R
, você adiciona os custos aoCondicionais
Dado um programa
P
do formulárioif A then Q else R end
, os custos dependem do estado:Em geral, a avaliação
A
pode muito bem mudar o estado, daí a atualização para os custos de cada filial.For-Loops
Dado um programa
P
do formuláriofor x = [x1, ..., xk] do Q end
, atribua custosonde é o estado antes do processamento para obter valor , ou seja, após a iteração ter sido definida como , ..., .ψi
Q
xi
x
x1
xi-1
Observe as constantes extras para manutenção de loop; a variável do loop deve ser criada ( ) e atribuída seus valores ( ). Isso é relevante, poiscinit_for cstep_for
xi
pode ser caro efor
loop com corpo vazio (por exemplo, depois de simplificar em uma melhor configuração com um custo específico) não terá custo zero se executar iterações.While-Loops
Dado um programa
P
do formuláriowhile A do Q end
, atribua custosAo inspecionar o algoritmo, essa recorrência costuma ser bem representada como uma soma semelhante à dos for-loops.
Exemplo: considere este pequeno algoritmo:
Ao aplicar a regra, obtemos
com alguns custos constantes para as declarações individuais. Assumimos implicitamente que estes não dependem do estado (os valores de e ); isso pode ou não ser verdade na "realidade": pense em transbordamentos!c…
i
x
Agora temos que resolver essa recorrência para . Observamos que nem o número de iterações, nem o custo do corpo do loop dependem do valor de , para que possamos eliminá-lo. Ficamos com esta recorrência:C1,4
i
Isso resolve com meios elementares para
reintroduzir o estado completo simbolicamente; se , então .ψ={…,x:=5,…} ψ(x)=5
Chamadas de procedimento
Dado um programa
P
do formulárioM(x)
para alguns parâmetros emx
queM
é um procedimento com o parâmetro (nomeado)p
, atribua custosObserve novamente a constante extra (que pode de fato depender de !). As chamadas de procedimento são caras devido à maneira como são implementadas em máquinas reais e às vezes dominam o tempo de execução (por exemplo, avaliando a recorrência do número de Fibonacci ingenuamente).ccall ψ
Descrevo alguns problemas semânticos que você possa ter com o estado aqui. Você desejará distinguir o estado global e o local para chamadas de procedimento. Vamos supor que passamos apenas para o estado global aqui e obtemos
M
um novo estado local, inicializado definindo o valor dep
parax
. Além disso,x
pode ser uma expressão que (geralmente) supomos que seja avaliada antes de ser aprovada.Exemplo: considere o procedimento
De acordo com as regras, obtemos:
Observe que desconsideramos o estado global, pois
fac
claramente não acessa nenhum. Essa recorrência específica é fácil de resolver paraNós cobrimos os recursos de idioma que você encontrará no pseudo-código típico. Cuidado com os custos ocultos ao analisar pseudo-código de alto nível; em caso de dúvida, desdobre. A notação pode parecer complicada e certamente é uma questão de gosto; os conceitos listados não podem ser ignorados. No entanto, com alguma experiência, você poderá ver imediatamente quais partes do estado são relevantes para qual medida de custo, por exemplo, "tamanho do problema" ou "número de vértices". O resto pode ser descartado - isso simplifica significativamente as coisas!
Se você acha que agora isso é muito complicado, saiba: é ! Obter custos exatos de algoritmos em qualquer modelo que seja tão próximo de máquinas reais que permita previsões de tempo de execução (mesmo as relativas) é um esforço árduo. E isso nem sequer considera cache e outros efeitos desagradáveis em máquinas reais.
Portanto, a análise de algoritmos é frequentemente simplificada a ponto de ser matematicamente tratável. Por exemplo, se você não precisar de custos exatos, poderá superestimar ou subestimar a qualquer momento (para limites superiores ou inferiores): reduzir o conjunto de constantes, livrar-se de condicionais, simplificar somas e assim por diante.
Uma nota sobre custo assintótico
O que você normalmente encontrará na literatura e nas redes é a "análise Big-Oh". O termo apropriado é análise assintótica , o que significa que, em vez de derivar custos exatos, como fizemos nos exemplos, você atribui os custos apenas a um fator constante e no limite (grosso modo, "para grandes ").n
Isso é (geralmente) justo, pois declarações abstratas têm alguns custos (geralmente desconhecidos) na realidade, dependendo da máquina, sistema operacional e outros fatores, e tempos de execução curtos podem ser dominados pelo sistema operacional que está configurando o processo em primeiro lugar e outros enfeites. Então você fica com alguma perturbação.
Aqui está como a análise assintótica se relaciona com essa abordagem.
Identifique operações dominantes (que induzem custos), ou seja, operações que ocorrem com mais frequência (até fatores constantes). No exemplo do Bubblesort, uma opção possível é a comparação na linha 5.
Como alternativa, vincule todas as constantes para operações elementares pelo respetivo máximo (de cima). mínimo (abaixo) e faça a análise usual.
Certifique-se de entender o significado dos símbolos Landau . Lembre-se de que esses limites existem para todos os três casos ; usar não implica uma análise do pior caso.O
Leitura adicional
Existem muitos outros desafios e truques na análise de algoritmos. Aqui estão algumas leituras recomendadas.
Como descrever algoritmos, provar e analisá-los?
Como podemos assumir que operações básicas sobre números levam tempo constante?
O que constitui uma unidade de tempo na análise de tempo de execução?
Existem muitas perguntas marcadas como análise de algoritmo que usam técnicas semelhantes a essa.
fonte
Contagens de declarações de execução
Existe outro método, defendido por Donald E. Knuth em sua série The Art of Computer Programming . Em contraste com a tradução de todo o algoritmo em uma fórmula , ele funciona independentemente da semântica do código no lado "juntando as coisas" e permite ir para um nível mais baixo somente quando necessário, começando pela visualização "olho de águia". Cada declaração pode ser analisada independentemente do restante, levando a cálculos mais claros. No entanto, a técnica se presta bem a códigos bastante detalhados, e não a pseudo-códigos de nível superior.
O método
É bastante simples em princípio:
Calcular custos totais
Você pode inserir estimativas e / ou quantidades simbólicas a qualquer momento, enfraquecendo a resp. generalizando o resultado de acordo.
Esteja ciente de que a etapa 3 pode ser arbitrariamente complexa. Geralmente é lá que você precisa trabalhar com estimativas (assintóticas) como " " para obter resultados.e77∈O(nlogn)
Exemplo: pesquisa em profundidade
Considere o seguinte algoritmo gráfico-transversal:
Assumimos que o gráfico (não direcionado) é fornecido por listas de adjacência nos nós . Seja o número de arestas.{0,…,n−1} m
Apenas olhando para o algoritmo, vemos que algumas instruções são executadas com a mesma frequência que outras. Introduzimos alguns espaços reservados , e para as contagens de execução :A B C ei
Em particular, pois todas as chamadas recursivas na linha 8 causam uma chamada na linha 3 (e uma é causada pela chamada original de ). Além disso, porque a condição deve ser verificada uma vez por iteração, mas novamente para que seja deixada.e8=e3−1 e6=e5+e7
foo
dfs
while
É claro que . Agora, durante uma prova de correção, mostraríamos que é executado exatamente uma vez por nó; isto é, . Porém, iteramos sobre todas as listas de adjacências exatamente uma vez e todas as arestas implicam duas entradas no total (uma para cada nó do incidente); obtemos iterações no total. Usando isso, derivamos a seguinte tabela:A=1 B=n C=2m
foo
Isso nos leva a custos totais de exatamente
Instanciando valores adequados para o , podemos derivar custos mais concretos. Por exemplo, se quisermos contar acessos à memória (por palavra), usaríamosCi
e pegue
Leitura adicional
Veja no final da minha outra resposta .
fonte
A análise de algoritmos, como a prova de um teorema, é amplamente uma arte (por exemplo, existem programas simples (como o problema de Collatz ) que não sabemos como analisar). Podemos converter um problema de complexidade de algoritmo em um matemático, conforme respondido de maneira abrangente por Raphael , mas, a fim de expressar um limite ao custo de um algoritmo em termos de funções conhecidas, resta:
fonte