Wenn ich die Zeitkomplexität der Zusammenführungssortierung analysiere, weiß ich, dass, da es O (log (n)) Ebenen und jede Ebene eine O (n) Operation gibt, die gesamte Zeitkomplexität O (nlog (n)) sein sollte. .Mergesort Komplexität O (nlogn) + O (n)?
Allerdings nicht geteilt O (n) insgesamt? Jede Teilung der Menge von Elementen nimmt O (1) an, aber du teilst insgesamt O (n) Mal, also nimmt der trennende Teil der Zusammenführungs-Sortierung nicht O (n) an? Zum Beispiel, wenn Sie 8 Elemente haben, müssen Sie 7 mal teilen und wenn Sie 16 Elemente haben, müssen Sie 15 mal teilen.
Also, sollte nicht die gesamte Merge Sortierzeit Komplexität technisch sein O (nlog (n)) + O (n)? Ich weiß, dass O (nlog (n) + n) dasselbe ist wie O (nlog (n)), aber niemand scheint dies in der Erklärung der Komplexität der Mischsortierzeit zu erwähnen.
Sie wissen, dass sie gleich sind, aber nicht verstehen, warum niemand so sagt? –
Ich denke nur, dass meine Logik hinter dem Löschprozess O (n) fehlerhaft sein kann, da ich nirgends sehen kann, dass der Löschteil O (n) ist, aber letztendlich am Ende ignoriert wird. – David
Das hast du nicht gefragt; Sie haben gefragt, warum ein O (n) -Begriff für einen O (n log n) -Algorithmus ignoriert wurde, und es ist der gleiche Grund, warum ein Sub-O (n log n) (z. B. O (1)) ignoriert wird erklärt und Sie behaupten bereits zu verstehen. –