Kommunauty
Connexion
Inscription

La récursivité en PHP


Vanyali Messages : 1298

Non, en fait la version itérative de ta fonction récursive sera aussi en O(log(N)) mais l'appel d'une fonction a un plus gros cout qu'une simple boucle. Mais le problème c'est justement de trouver un moyen de résoudre le problème récursif en itératif avec une même complexité temporelle ça reste de la théorie pour pas mal d'algorithmes .

jeudi 14 novembre 2013

Sypix Messages : 892

Pratique pour lister des arborescences aussi (ça je vois absolument pas comment le faire en itératif )

jeudi 14 novembre 2013

Mizur Messages : 6617

Mais le problème c'est justement de trouver un moyen de résoudre le problème récursif en itératif avec une même complexité temporelle ça reste de la théorie pour pas mal d'algorithmes

Justement je conçois pas trop... L'intéret de la recursivité c'est justement que ça va plus vite, pour une grande partie des langages. (sinon équivalent).

En itératif comment tu peux faire un tri en temps log(N) ?

jeudi 14 novembre 2013

Vanyali Messages : 1298

En fait si tu veux récursif c'est pas plus rapide mais plus facile.

Déjà, il n'existe pas de tri en O(log(n)) parce qu'il doit au moins être en O(n) pour parcourir tout le tableau. Sauf pour les algorithmes théorique, inutilisable avec des machines, par exemple, le bogosort version quantique est en temps constant, car il est capable de générer toute les solutions en même temps , le spagheti sort qui demande autant de processeur que d'entrée dans le tableau est en O(n) et en O(log(n)) il y en a un mais je ne connais pas le principe .

mais en O(n log(n)), le tri par tas est itératif et a la même complexité temporelle que le quick sort c'est à dire O(n log(n)). mais il est légèrement moins efficace. Cependant, contrairement au tri rapide, il n'admet pas de pire cas en O(n²) une optimisation du tri rapide consiste à utiliser un mixe entre le tri par tas et le tri rapide suivant la taille du tableau pour annuler les désavantages des deux.

jeudi 14 novembre 2013 (Dernière édition dimanche 17 novembre 2013)

Homer Messages : 1861

J'ai peur de demander un exemple de code

vendredi 15 novembre 2013 (Dernière édition vendredi 15 novembre 2013)

Vanyali Messages : 1298

Je peut te donner les algo, ils sont dispo sur wikipedia, après, pour le code dans un langage précis, c'est juste une traduction

Mais tu veux un exemple pour quel tri ?

vendredi 15 novembre 2013

Homer Messages : 1861

aucune idée, juste un exemple de récursivité.

J'ai une idée dans ma tête mais je dois être très loin du sujet

vendredi 15 novembre 2013

Vanyali Messages : 1298

ah ok, juste de récursivité.

l'exemple qu'on montre généralement c'est ça :


Algorithme factorielle
Entrée : n un entier
Sortie : un entier
Début
     Si n = 1 ou n = 0 Alors
          Retourne 0
     Sinon
          Retourne n* factorielle(n-1)
     Fin Si
Fin
vendredi 15 novembre 2013

Ideophage Messages : 115

Salut !

En ce qui concerne la dérécursification, il suffit au pire de gérer l'appel des fonctions à la main avec une pile.

J'avais codé un parseur de markdown avec PHP, les appels de fonction sont très couteux dans ce langage. Du coup, quand les performances ont une importance, il vaut peut-être mieux faire du code un peu obscur. À l'EPITECH, leur « norme » dit que les fonctions ne doivent pas faire plus de 20 lignes. Ça encourage à la modularité (ou à l'obfuscation ?), et c'est bien, mais en PHP, il peut parfois être mieux de ne pas modulariser. Une anecdote : je ne me souviens plus des détails, mais j'ai vu quelque part qu'un certain programme (codé en C) passait la *moitié* du temps dans des appels de fonctions sur une certaine machine ! <-- edit : pas certain pour le C, mais je crois bien. Je n'arrive plus à retrouver la source.

Pour le spaghetti sort (Que la Pasta soit avec vous !), il existe une version temporelle : le sleep sort. Il lance pour chaque entrée un processus qui attend un temps proportionnel au nombre puis l'affiche. Et il y a une version dessein intelligent (Que la Pasta soit avec vous !) de l'algo reposant sur l'interprétation (foireuse ?) de la physique quantique. Il est en temps linéaire : http://www.dangermouse.net/esoteric/intelligentdesignsort.html Il y a aussi des gens qui ont fait un logiciel qui permet de visualiser et d'écouter des algos de tri : http://panthema.net/2013/sound-of-sorting/

Un peu hors sujet, les trucs ésotériques.

Vanyali > Tu as écrit O(ln N) à la place de O(N), pour parcourir le tableau.

dimanche 17 novembre 2013 (Dernière édition dimanche 17 novembre 2013)

Vanyali Messages : 1298

Ah ouais, épique fail, ma phrase n'avait aucun sens du coup

dimanche 17 novembre 2013

Page suivante »