Einfache Big O Fragen

Question

4. Hash-Tabelle (Array-Liste für Überlaufbehandlung)

ein. Find O()

b. Einfügen O()

c. Ascend (Druckwerte aufsteigend sortiert) O()

5. binärer Suchbaum

ein. Löschen O()

b. Aufsteigend (Druckwerte aufsteigend sortiert) O()

Meine Antwort: 4. a. Die Suche muss O (n) sein, da der Überlauf möglicherweise dazu führen kann, dass er durch die gesamte hashmap geht.

b. wie a, O (n)

c. Meine Vermutung ist hier O (nlogn), da es eine Art Heap-Sortierung verwenden kann, um zu sortieren und zu drucken ist nur n, also

5. a. O (n) nur weil ich mich an das Buch erinnere

b. meine Schätzung ist die gleiche wie Frage 4, nlogn seit Heapsort verwendet werden kann

Ich bin ich richtig? Danke!

Answer 1

Es ist schwer, dies ohne ein bisschen mehr kontextuelle Informationen zu beantworten, aber in der Regel für Hash-Tabellen finden und einfügen sind O (1).

Also meine Antworten wären:

4a. O (1)

4b. O (1)

4c. O (n log n)

5a. O (log n)

5b. O (n log n)