Big O, comment calculez-vous/approximatif?

La plupart des gens avec un diplôme en CS savez certainement ce que Big O est synonyme de.
Il nous aide à mesurer le degré de (in)efficace, un algorithme est vraiment et si vous savez dans dans quelle catégorie le problème que vous essayez de résoudre réside dans, que vous pouvez découvrir si il est encore possible de faire sortir le petit plus de performance.1

Mais je suis curieux, comment faire vous calculer ou approximative de la complexité des algorithmes de votre?

1 mais comme ils le disent, n'en abusez pas, l'optimisation prématurée est la racine de tous les maux, et l'optimisation sans cause justifiée faut mériter ce nom.

Peut-être que vous n'avez pas réellement besoin pour améliorer votre algorithme de complexité, mais vous devriez au moins être en mesure de calculer, pour décider...
J'ai trouvé cette explication claire de Big O, Gros Omega, et les Grandes Thêta: xoax.net/comp/sci/algorithms/Lesson6.php
-1: Soupir, un autre abus de BigOh. BigOh est juste un asymptotique limite supérieure et pourrait être utilisé pour quoi que ce soit et n'est pas seulement CS liés. Parler BigOh comme si il y en a un unique est vide de sens (Un temps linéaire algorithme est O(n^2), O(n^3), etc). En disant cela nous aide mesure efficacité est trop trompeuse. Aussi, quel est le lien pour la complexité des classes? Si vous êtes intéressé, est des techniques pour calculer le temps d'exécution des algorithmes, comment est-ce pertinent?
Big-O ne mesure pas l'efficacité, et il mesure les performances d'un algorithme échelles avec la taille (il peut s'appliquer à d'autres choses que la taille est trop mais c'est ce qui nous intéresse ici) et que seulement asymptotiquement, donc si vous êtes hors de la chance un algorithme avec un "petit" big-O peut être plus lent (si le Big-O s'applique à des cycles) qu'un autre jusqu'à ce que vous atteindre un très grand nombre.
Le choix d'un algorithme sur la base de son Grand-O complexité est généralement une partie essentielle de la conception du programme. Il est très certainement pas un cas de "l'optimisation prématurée", qui en tout cas est tellement abusé de la citation sélective.

OriginalL'auteur sven | 2008-08-06