Analyse d'algorithme - Big O 0ation

Question

Quelle est une bonne stratégie pour déterminer la durée d'exécution (notation Big O) des structures de données et des algorithmes. Je suis la suivante pour comprendre les temps d'exécution pour et j'ai difficulté à déterminer ce que ce serait.

AINC est un tableau contenant n entiers disposés par ordre croissant. AD est un tableau contenant n entiers disposés par ordre décroissant.

AR est un tableau contenant n entiers dans un ordre aléatoire.

Q est une file d'attente implémentée sous forme de liste chaînée et contenant des éléments p.

LINK est une liste chaînée contenant n nœuds.

CIRC est une liste circulaire contenant n éléments, où C pointe vers le dernier élément. T est un arbre de recherche binaire contenant n nœuds.

a) Recherche d'un élément dans AINC à l'aide de la recherche linéaire.

b) Supprimer le 10ème nœud de la liste LINK liée.

c) Appel d'une fonction qui utilise Q et appelle dequeue m fois.

d) Insertion d'un élément à la fin de la liste CIRC.

e) Supprimer le dernier élément de CIRC.

f) Pour trouver le plus grand élément de T.

g) Détermination de la hauteur de T.

h) amène le SelectionSort d'appel (INAC, n).

i) Faire deux appels l'un après l'autre. Le premier appel est mergesort (AD, n), suivi de l'appel insertionsort (AD, n). J) Conversion d'un entier décimal num en son équivalent binaire.

*** Ce n'est pas hw. Je me prépare à un examen.

Answer 1

(Depuis l'OP a demandé pour elle)

Vous ramasser un morceau de papier.

• Si votre question mentionne un certain nombre (par exemple, répéter n fois, ou trouver le n -ème dernier élément):

Vous effectuez la main sur le papier les opérations nécessaires pour effectuer la action mentionnée lorsque ce nombre est 1 (le cas échéant).

Vous répétez pour chacune des valeurs suivantes de ce nombre: 2, 10, 20, 100, 1000 et 10000. Juste pour les coups de pied, vous pouvez également essayer avec le nombre réel mentionné dans la question.

Vous mesurez le temps qu'il a fallu pour chaque cas et vous tracer sur un morceau de papier (oh, un spreadsheed ferait également, je suppose) la fonction t(n), où t est le temps, et n le nombre. Vous parcourez vos vieux livres de mathématiques pour identifier la courbe. Par exemple. Si c'est un parabolique, vous avez probablement un algorithme O (n^2) entre vos mains.

• Si votre question ne mentionne pas de numéro:

Répétez la procédure précédente ci-dessus en utilisant 2, 10, 20, 100, 1000 et 10000 éléments dans une structure de données mentionnée (tableau, liste, etc.). Si la "structure" est un nombre, utilisez simplement autant de chiffres.

REMARQUE:

Si vous parvenez à visualiser la procédure ci-dessus sans tourner la moitié des arbres restants de cette planète en papier ou avoir votre main tomber, alors vous êtes à mi-chemin vers une technique intuitive semi-décente . Cependant, vous devriez lire sur la bonne façon mathématique de faire face à cela, cependant - l'intuition ne peut vous mener que jusqu'à présent dans ce cas.

En outre, la plupart des exemples que vous avez mentionnés sont si basiques que la plupart des gens mémorisent (et un peu plus tard, ils connaissent simplement leur complexité). Vous devriez vraiment avoir un livre ou des notes décentes à ce sujet. Introduction to Algorithms est un beau, gros livre d'introduction sur ce champ.

EDIT:

Recherche de algorithms and complexity dans Google produit également un tas de résultats intéressants. Vous devriez l'essayer de temps en temps ...

Answer 2

Si vous êtes nouveau à l'analyse Big O et avez un peu de temps (2,5 heures), je vous recommande de regarder les deux premiers lectures de cette classe d'algorithmes livrés par Leiserson lui-même.