A complexidade do algoritmo é projetada para ser independente dos detalhes de nível inferior, mas é baseada em um modelo imperativo, por exemplo, o acesso à matriz e a modificação de um nó em uma árvore levam o tempo O (1). Este não é o caso em linguagens funcionais puras. A lista Haskell leva tempo linear para acesso. Modificar um nó em uma árvore envolve fazer uma nova cópia da árvore.
Deve haver uma modelagem alternativa da complexidade do algoritmo para linguagens funcionais?
STmônadas).Respostas:
Se você assumir que o calculus é um bom modelo de linguagens de programação funcional, então pode-se pensar: o λ- calculus tem uma noção aparentemente simples de complexidade de tempo: basta contar o número de etapas de redução β ( λ x . M ) N → M [ N / x ] .λ λ β ( λ x . M) N→ M[ N/ x]
Mas isso é uma boa medida de complexidade?
Para responder a essa pergunta, devemos esclarecer o que entendemos por medida de complexidade em primeiro lugar. Uma boa resposta é dada pela tese de Slot e van Emde Boas : qualquer boa medida de complexidade deve ter uma relação polinomial com a noção canônica de complexidade de tempo definida usando máquinas de Turing. Em outras palavras, deve haver um 'razoável' que codifica A partir de X termos -calculus para máquinas Turing, tal para alguns polinómio p , que é o caso que, para cada termo M de tamanho | M | : M reduz para um valor em p ( | M |t r ( . ) λ p M | M| M etapas de redução β exatamente quando t r ( M ) se reduz a um valor emetapas p ( | t r ( M ) | ) de uma máquina de Turing.p ( | M| ) β t r ( M) p ( | t r ( M) | )
Durante muito tempo, não ficou claro se isso pode ser alcançado no cálculo λ. Os principais problemas são os seguintes.
O artigo " Beta Reduction is Invariant, Indeed ", de B. Accattoli e U. Dal Lago, esclarece a questão, mostrando uma codificação 'razoável' que preserva a classe P de complexidade das funções de tempo polinomial, assumindo reduções de chamada por nome mais à esquerda . O insight principal é que a explosão exponencial só pode acontecer por razões 'desinteressantes' que podem ser derrotadas pelo compartilhamento adequado. Em outras palavras, a classe P é a mesma, independentemente de você a definir contando as etapas da máquina de Turing ou as reduções (mais à esquerda na extrema) .β
Não tenho certeza de qual é a situação para outras estratégias de avaliação. Não sei que um programa semelhante foi realizado para complexidade do espaço.
fonte
Não, não mesmo. Sempre contamos operações elementares em alguns modelos de máquinas:
Você provavelmente estava pensando em toda a / Θ / O -business. Embora seja verdade que você possa abstrair alguns detalhes de implementação com os assintóticos Landau, você não se livra do impacto do modelo da máquina. Os algoritmos têm tempos de execução muito diferentes, digamos, TMs e RAMs - mesmo se você considerar apenas classes Θ !Ω Θ O Θ
Portanto, sua pergunta tem uma resposta simples: conserte um modelo de máquina e quais "operações" contar. Isso lhe dará uma medida. Se você deseja que os resultados sejam comparáveis aos algoritmos não funcionais, seria melhor compilar seus programas na RAM (para análise de algoritmos) ou TM (para teoria da complexidade) e analisar o resultado. Teoremas de transferência podem existir para facilitar esse processo.
fonte
O(1)quando é realmenteO(log ab)Em vez de formular sua medida de complexidade em termos de alguma máquina abstrata subjacente, você pode incluir o custo nas próprias definições de linguagem - isso é chamado de Dinâmica de Custo . Um atribui um custo a todas as regras de avaliação na linguagem, de maneira composicional - ou seja, o custo de uma operação é uma função do custo de suas subexpressões. Essa abordagem é mais natural para linguagens funcionais, mas pode ser usada para qualquer linguagem de programação bem definida (é claro que a maioria das linguagens de programação infelizmente não está bem definida).
fonte