Aprendi hoje que a análise de algoritmos difere com base no modelo computacional. É algo em que nunca pensei ou ouvi falar.
Um exemplo dado a mim, que o ilustrou ainda mais, pelo usuário @chi foi:
Por exemplo, considere a tarefa: dado retorne . Na RAM, isso pode ser resolvido em pois o acesso ao array é de tempo constante. Usando TMs, precisamos varrer toda a entrada, para que seja
Isso me faz pensar sobre linguagens funcionais; Pelo meu entendimento, "linguagens funcionais estão intimamente relacionadas ao cálculo lambda" (de um comentário de Yuval Filmus aqui ). Portanto, se as linguagens funcionais são baseadas no cálculo lambda, mas são executadas em máquinas baseadas em RAM, qual é a maneira correta de realizar análises de complexidade em algoritmos implementados usando estruturas e linguagens de dados puramente funcionais?
Não tive a oportunidade de ler Estruturas de dados puramente funcionais, mas examinei a página da Wikipedia sobre o assunto e parece que algumas estruturas de dados substituem as matrizes tradicionais por:
"Matrizes podem ser substituídas por mapa ou lista de acesso aleatório, que admite implementação puramente funcional, mas o tempo de acesso e atualização é logarítmico."
Nesse caso, o modelo computacional seria diferente, correto?
Respostas:
Depende da semântica da sua linguagem funcional. Você não pode fazer análise de algoritmo em linguagens de programação isoladamente, porque não sabe o que as declarações realmente significam. A especificação para o seu idioma precisa fornecer semântica suficientemente detalhada. Se o seu idioma especificar tudo em termos de cálculo lambda, você precisará de alguma medida de custo para reduções (eles são O (1) ou dependem do tamanho do termo que você reduz?).
Eu acho que a maioria das linguagens funcionais não faz dessa maneira e, em vez disso, fornece instruções mais úteis como "chamadas de função são O (1), acrescentadas ao cabeçalho de uma lista é O (1)", coisas assim.
fonte