J'ai souvent été légèrement perturbé par des algorithmes récursifs qui semblent nécessiter des sauts magiques (avec une forte dose de notation rétrécie née d'une pénurie d'encre) de logique.Analyser des algorithmes récursifs
Je me rends compte que l'alternative est de simplement mémoriser la notation Big O pour tous les algorithmes communs mais à un certain point, cette approche échoue. Par exemple, je suis heureux de divulguer la performance pour le tri à bulles, le tri par insertion, l'insertion/suppression d'arbre binaire, le mergesort et le quicksort, mais ne me demandez pas de calculer les arbres AVL ou l'algorithme de Djikstra. de ma tête.
Où puis-je obtenir:
- Une discussion sur l'analyse de l'algorithme récursif qui utilise des mots au lieu d'une profusion de symboles
- problèmes de pratique pour confirmer que ma compréhension nouvellement obtenue est correcte
Exemple:
Bad:
Sigma ve T (1 + cv)
équivalent 'bon' possible:
La quantité de travail nécessaire pour 1 nœud dans l'arbre (qui est 1 + le # d'enfants d'un noeud), qui est ensuite exécuté une fois pour chaque élément de l'arborescence où le nœud d'origine est la racine.
commentaire Side:
Je pourrais simplement regarder une vidéo pour chaque algorithme, car il n'y a pas moyen de faire son tour de la voix dans un indice (ou l'un des autres contorsions) mais je pense que cela prendrait un montant démesuré du temps par rapport à la lecture des descriptions textuelles.
Mise à jour:
est ici 1 source de problèmes résolus: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/ (ce attaque 2 ci-dessus)
Vous devriez apprendre à vous familiariser avec la communication de ces idées dans des symboles. C'est efficace, précis et le langage que presque tout le monde utilise. – jason
@Jason: Si vous êtes un étudiant ou un étudiant en mathématiques ou en théorie. Pour un bon programmeur, il devrait suffire de comprendre le sens. – Bytemain
+1 au point de Jason. Pour se mettre à l'aise (et mieux que la plupart des gens, en fait!) Avec la notation et l'analyse, je recommande le merveilleux livre * [Mathématiques concrètes: une fondation pour l'informatique] (http://en.wikipedia.org/wiki/Concrete_Mathematics). * Juste les deux premiers chapitres devraient suffire (plus éventuellement le dernier), mais c'est tellement bien écrit qu'il est difficile de résister à la lecture des autres chapitres. – ShreevatsaR