Algorithmus-Analyse - Große O-Notation

Question

Was ist eine gute Strategie, um die Laufzeit (Big-O-Notation) von Datenstrukturen und Algorithmen zu bestimmen. Ich habe die folgenden, um herauszufinden, die Laufzeiten für und ich habe Schwierigkeiten zu bestimmen, was es sein würde.

AINC ist ein Array mit n ganzen Zahlen in aufsteigender Reihenfolge.

AD ist ein Array mit n ganzen Zahlen in absteigender Reihenfolge.

AR ist ein Array mit n ganzen Zahlen in zufälliger Reihenfolge.

Q ist eine Warteschlange, die als verkettete Liste implementiert ist und p Elemente enthält.

LINK ist eine verknüpfte Liste mit n Knoten.

CIRC ist eine kreisförmige verkettete Liste mit n Elementen, wobei C auf das letzte Element zeigt.

T ist ein binärer Suchbaum, der n Knoten enthält.

a) Suche nach einem Element in AINC mit linearer Suche.

b) Löschen des 10. Knotens der verknüpften Liste LINK.

c) Aufruf einer Funktion, die Q verwendet, und Aufrufe m-mal aus der Warteschlange herausnehmen.

d) Einfügen eines Elements am Ende der Liste CIRC.

e) Löschen des letzten Elements von CIRC.

f) Finden der größten Element der T.

g) Bestimmen der Höhe von T.

h) der an den Anruf SelectionSort (AINC, n).

i) Zwei Anrufe nacheinander tätigen. Der erste Aufruf ist Mergesort (AD, n), gefolgt von dem Aufrufeinfügungsort (AD, n).

j) Konvertieren einer Dezimalzahl num in ihre binäre Entsprechung.

*** Dies ist nicht hw. Ich bereite mich auf eine Prüfung vor.

Answer 1

(Da die OP danach gefragt)

Sie nehmen ein Stück Papier.

• Wenn Ihre Frage eine Reihe erwähnt (zB wiederholen n mal, oder finden Sie das n -te letzte Element):

Sie von Hand auf Papier führen die Operationen benötigt die zur Durchführung Aktion, wenn diese Zahl 1 ist (falls zutreffend).

Sie wiederholen für jeden der folgenden Werte dieser Zahl: 2, 10, 20, 100, 1000 und 10000. Nur für Tritte können Sie auch versuchen, mit der tatsächlichen Nummer in der Frage erwähnt.

messen Sie die Zeit, die Sie für jeden Fall nahm und sie dann auf ein Stück Papier plotten (oh, eine Tabellenkalkulation würde auch tun, nehme ich an) die Funktion t(n), wo t die Zeit ist, und n die Zahl.

Sie sehen durch Ihre alten Mathe Bücher, um die Kurve zu identifizieren. Z.B. Wenn es ein Parabol ist, haben Sie höchstwahrscheinlich einen O (n^2) -Algorithmus in Ihren Händen.

• Wenn Ihre Frage nicht erwähnt, eine Zahl:

Wiederholen Sie das vorherige Verfahren oben von 2 unter Verwendung von, 10, 20, 100, 1000 und 10000 Elementen in jeder Datenstruktur erwähnt (Array, Liste usw.). Wenn die "Struktur" eine Zahl ist, verwenden Sie einfach so viele Ziffern.

HINWEIS:

Wenn Sie die oben beschriebene Prozedur ohne Drehen Hälfte dieses Planeten verbliebenen Bäume in Papier oder mit der Hand fällt verwalten sichtbar zu machen, dann sind Sie auf halbem Weg in Richtung auf eine halbwegs anständige intuitive Technik sind .

Sie sollten sich jedoch auf die richtige mathematische Art und Weise damit befassen - Intuition kann Sie in diesem Fall nur so weit bringen.

Darüber hinaus sind die meisten Beispiele, die Sie erwähnt haben, so einfach, dass die meisten Menschen nur merken (und ein bisschen später nur wissen) ihre Komplexität. Du solltest wirklich ein Buch oder ein paar anständige Notizen dazu bekommen. Introduction to Algorithms ist eine nette, große Fett einleitende Buch über dieses Feld.

EDIT:

für algorithms and complexity in Google Suche erzeugt auch einen ganzen Haufen von interessanten Ergebnissen. Sie sollten es einmal in einer Weile versuchen ...

Answer 2

Wenn Sie neu zu Big O-Analyse sind und etwas Zeit haben (2,5 Stunden), würde ich empfehlen, die ersten beiden lectures dieser Algorithmen-Klasse von Leiserson selbst geliefert.