bon texte sur l'analyse de l'ordre

Question

En tant que programmeur informatique autodidacte, je suis souvent à une perte pour estimer la valeur O() pour une opération particulière. Ouais, je sais d'avance ce que sont les plus importants, comme pour les recherches et les types principaux, mais je ne sais pas comment en calculer un quand quelque chose de nouveau arrive, à moins que ce soit aveuglant. Y a-t-il un bon site web ou un bon texte qui explique comment faire cela? Heck, je ne sais même pas ce que les informaticiens appellent, donc je ne peux pas le google.

Answer 1

Si vous voulez vraiment apprendre ce sujet, alors vous avez probablement besoin d'une théorie standard/manuel d'algorithmes. Je ne connais pas de site Web qui puisse réellement vous enseigner l'analyse de complexité (la «complexité» ou la «complexité temporelle» est la façon dont vous appelez ces valeurs O(), vous pourriez aussi vouloir google pour «analyse d'algorithmes» ou «introduction à algorithmes "ou autres".

Mais avant cela - une option gratuite. Il y a des diapositives d'un cours donné par Erik Demaine et Charles Leiserson au MIT, qui sont gratuits et très bien. J'essaierais certainement de les lire et de voir si cela fonctionne pour vous. Ils sont here.

Maintenant, les manuels:

Le choix classique pour un manuel est le livre de Cormen et al Introduction to Algorithms (il pourrait y avoir une version pas cher disponible pour acheter here et je me souviens avoir vu une version gratuite (éventuellement illégal) en ligne, mais je ne me souviens pas où).

Un livre plus récent et de style moderne, qui est plus amusant à lire et un meilleur choix, est le Algorithm Design de Kleinberg et Tardos.

Voici quelques sites Web avec des informations (je suis arrivé ce par googler "analyse d'algorithme notes de cours" sans les guillemets):

• Algorithms Lecture Notes
• Lecture notes by Steve Skiena

Ce qui précède est écrit par un théoricien de l'informatique. Ainsi, les programmeurs ou d'autres personnes pratiques peuvent avoir des opinions différentes.

Answer 2

Il est ce qu'on appelle Big O Notation, et il est utilisé dans Computational Complexity Theory.

Les articles wikipedia sont un très bon point de départ, tout comme la bibliographie en bas de la page.

Answer 3

Introduction to Algorithms est le texte standard utilisé dans la plupart des universités. Je l'ai utilisé et je peux recommander ces chapitres sur l'analyse des commandes. Je commencerais par les articles de la réponse de Tim Howland.

Answer 4

Il est appelé l'analyse d'algorithmes et est une science en soi. Jetez un oeil à quelques-uns des livres here

Answer 5

Vos liens me prend à un site dans russe qui semble vouloir un userid et mot de passe. Erreur légitime, ou troll?Paul Tomblin

Le site est en bulgare et vous ne devriez pas avoir besoin d'un mot de passe pour accéder à la liste des fichiers que je Linked et télécharger certains d'entre eux. À moins bien sûr qu'il y ait une reprise d'accès pour les IP de l'extérieur de la Bulgarie, ce que je ne sais vraiment pas.

Désolé, je ne sais pas comment faire un commentaire.