Ich versuche, Hausaufgaben mit einem Freund zu machen, und eine Frage stellt die durchschnittliche Laufzeit von Suchen, Hinzufügen und Löschen für die lineare Suchmethode. Ich denke, es ist O (n), weil es bei einer bestimmten Anzahl von Knoten prüfen muss, bis es einen offenen Knoten zum Hinzufügen findet. Und beim Suchen beginnt es beim ursprünglichen Index und bewegt sich nach oben, bis es die gewünschte Nummer findet. Aber meine Freunde sagen, es ist O (1). Welcher hat Recht?
Wenn wir von asymptotischen Komplexitäten sprechen, berücksichtigen wir im Allgemeinen sehr große n. Nun zur Kollisionsverarbeitung in einer Hash-Tabelle sind einige der Methoden verkettet Hashing & amp; lineares Sondieren. In beiden Fällen können zwei Dinge passieren (die Ihnen bei der Beantwortung Ihrer Frage helfen können): 1. Möglicherweise müssen Sie die Größe der Hash-Tabelle ändern, damit sie voll wird. 2. Es kann zu Kollisionen kommen.
Im schlimmsten Fall hängt es davon ab, wie Sie Ihre Hash-Tabelle implementiert haben. Sagen Sie im linearen Suchlauf, dass Sie die Nummer nicht finden. Sie bewegen sich weiter und die Nummer, nach der Sie gesucht haben, war am Ende. Hier kommt die O (n) worst case Laufzeit. Wenn eine Kollision auftritt, sagen wir, dass wir die Schlüssel in einem ausgeglichenen Binärbaum gespeichert haben, so dass die Worst-Case-Laufzeit O (log n) wäre.
Jetzt, da ich zur besten Laufzeit komme, denke ich, dass es keine Verwirrung gibt, in jedem Fall wäre es O (1).
O (n) würde im schlimmsten Fall passieren und nicht im Durchschnitt einer gut entworfenen Hash-Tabelle. Wenn das im Durchschnitt geschieht, finden Hashtabellen keinen Platz in Datenstrukturen, denn dann würden ausgeglichene Bäume im Durchschnitt immer O (log n) ergeben, und ON TOP OF THE wird auch die Reihenfolge beibehalten.
Tut mir leid, dies zu sagen, aber leider hat dein Freund recht. Ihr Fall würde im schlimmsten Fall passieren.
Sehen Sie auch hier nach informativerem Material, dh die amortisierte Laufzeit: Zeit Komplexität der Hash-Tabelle
Tags und Links algorithm data-structures hashtable asymptotic-complexity