vue
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 : 6615 | 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 : 1925 | 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 : 1925 | 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 :
|
vendredi 15 novembre 2013
| |
Anonyme Messages : 0 | 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
|
Aperçu (pas encore publié) | |
Kommunauty © Tous droits réservés
Contact /
Charte & Mentions légales /
Hebergement gratuit /
Bon plan hébergement /
Aide B2i