Complexité dans les programmes Prolog?

Question

En Prolog, les problèmes sont résolus en utilisant le retour arrière. C'est un paradigme déclaratif plutôt qu'impératif (comme en C, PHP ou Python). Dans ce genre de langues vaut-il la peine de penser en termes de complexité? La façon naturelle de penser que vous pensez que les problèmes semblent être O (N^2) est que quelqu'un a pointé this question.

Answer 1

Il est important d'analyser la complexité dans n'importe quelle langue que ce soit prologue ou tout autre langage impératif. Cependant, je peux vous donner quelques conseils pour accélérer vos programmes prolog

1. Toujours Toujours essayer de rendre vos programmes récursifs. Cela permettra de s'assurer que votre programme ne manque pas de pile. Essayez d'utiliser couper et échouer dans vos programmes où vous savez que vous n'avez pas besoin d'autres réponses.
2. Essayez d'utiliser des accumulateurs.
3. Check out CLPFD, Il aide à réduire considérablement l'espace de recherche, ce qui accélère votre programme. Essentiellement, il élimine le mauvais choix avant que votre programme puisse faire marche arrière et perdre du temps à explorer ces choix.
4. Toujours écrire la meilleure règle de résultat en premier. (Cela dépend vraiment du problème, mais généralement la règle du meilleur cas va en premier).

Answer 2

Vous pouvez certainement analyser la complexité des programmes Prolog, comme n'importe quel autre langage. Ce problème particulier que vous avez lié pourrait être O (n^2). Mais tous les programmes Prolog n'auront pas cette complexité. Par exemple, vous pouvez facilement écrire un solveur SAT dans Prolog, et ce problème est NP-complet.

Answer 3

Cela dépend entièrement du problème.

par exemple. sommer une liste de nombres est O (N), autant que je sache.

sum([],0). 
sum(List,Total) :- 
    sum(List,0,Total). 

sum([],Total,Total). 
sum([Head|Rest],Accumulator,Total) :- 
    SoFar is Head + Accumulator, 
    sum(Rest,SoFar,Total). 

Les seules actions sont l'addition (« est ») et l'appel récursif, ce qui devrait être à la fois une valeur de 1 chacun. Ils seront tous deux effectués ~ une fois par item dans la liste, donc le total des actions devrait être ~ 2N, qui est O (N).