Laufzeitabschätzung Heap Erstellung?
Hey, also ich habe zwei Aufgaben:
3. Nutzen Sie das vorherige Ergebnis um die O(N) Absch ̈atzung zu zeigen.
4. Verfeinern Sie auf Θ(N). (Das ist einfach)
die drei habe ich dadurch gelöst, dass ich gesagt hab mit einer Eingabe der Länge N (N Elemente) beauche ich N Knoten. Für einen Binärbaum mit N knoten gilt: Bei einem vollständigen Binärbaum der Tiefe t, ist die Summe der Abstände aller Knoten zur Krone N − t − 1. Also muss ich im schlechtesten Fall Bei jedem neu aufgebauten Teilbaum jedes Element verschieben, also gehen ich jeden Pfad im Graph. Dadurch O(N-t-1) = O(N) (da N = 2^(t+1)-1 .
Wie geh ich an die 4 ran?
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Mathematik
also die WP sagt, dass „Big Theta“ eine obere und untere Schranke angibt... oder? in Formeln:
Was sagt dein Lehrbuch?
Woher ich das weiß:Studium / Ausbildung – Absolvent/Universität