Frage zu Summationen und der Θ-Notation von Laufzeiten

Question

Frage zu Summationen und der Θ-Notation von Laufzeiten

Summe
Algorithmen
Asymptotik
Mathematik

CheekyKontBrah

Ich glaube, ich verstehe das Konzept von Summationen und Θ-Notationen, aber ich verstehe die folgende Frage nicht wirklich.

Wenn ich es richtig verstanden habe, soll ich die Summationen (Funktionen links) aufschreiben und dann ihre Wachstumsreihenfolge mit den Funktionen rechts vergleichen (korrigiere mich, wenn ich falsch liege).

Jetzt ist der Teil, wo ich hängengeblieben bin: Ich bin mir nicht sicher, was ich mit den Summen machen soll.

Es gibt tatsächlich mehr Funktionen auf der linken Seite, aber ich habe sie gelöscht, damit die Frage weniger chaotisch aussieht.

Geben Sie hier die Bildbeschreibung ein

Antworten (1)

Frage zu Summationen und der Θ-Notation von Laufzeiten

Hubble · Answer 1

Es ist etwas seltsam, dass Ihr Summand keine beinhaltet $i$ 's, da summierst du aus $i=1$ bis zu $n$ . Vorausgesetzt, Sie haben keinen Fehler gemacht,

\begin{aligned} ich (N) & = \sum_{ich = 1}^{N} (4 + Protokoll N) = N (Protokoll N + 4) \end{aligned}

$\begin{align*} i(n) &= \sum_{i=1}^n (4 + \log n) = n(\log n + 4) \end{align*}$

Du hast ein $n\log n$ Laufzeit und a $4n$ Begriff. Wenn du das verstehst $\Theta$ -Notation Nun, Sie sollten in der Lage sein, dies zu beantworten. Bei den anderen Fragen sollten Sie die Summe erweitern, falls vorhanden, und prüfen, ob Sie sie ohne die Summe für die gebundene Analyse umschreiben können.

Danke, also muss ich im Grunde nur die Summationen erweitern und dann den Term mit der höchsten Ordnung nehmen, was die entsprechende Θ-Notationsfunktion wäre? Also wäre n(logn+4) Θ(n)?

Frage zu Summationen und der Θ-Notation von Laufzeiten

CheekyKontBrah

Antworten (1)

Hubble

CheekyKontBrah

Hubble

Was bedeutet das Wort „Skalierbarkeit“ in Bezug auf Big O?

Was genau macht den Worst-Case-Eingang verschiedener Sortieralgorithmen aus?

Formel zur Größenbestimmung, bei der eine Wachstumsrate die andere schlägt?

Laufzeit des Algorithmus bei gegebener zeitlicher Komplexität

Dominanter Begriff und Big Omega

Warum "Big O" berechnen, wenn wir nur die Anzahl der Schritte berechnen können?

Was sagt Big O dir eigentlich?

Wenn bi=ai+1−aibi=ai+1−aib_i = a_{i+1} - a_i, warum gilt aj−ai=bi+⋯+bj−1.aj−ai=bi+⋯+bj−1.a_j - a_i = b_{i}+\cdots+b_{j-1}. für 1≤i≤n−11≤i≤n−11 \leq i \leq n-1?

Quicksort-Laufzeit

Identität mit Doppelsumme mit Binomen