Als «asymptotics» getaggte Fragen

Ich mache eine Abschlussarbeit über den Nachweis der Richtigkeit des Programms zum Multiplizieren von 2 Matrizen mit Hoare-Logik. Dazu muss ich die Invariante für die verschachtelte Schleife für dieses Programm generieren: for i = 1:n for j = 1:n for k = 1:n C(i,j) = A(i,k)*B(k,j) + C(i,j); end end...

Ich wurde beauftragt, einige Wiederholungsrelationen zu lösen, und ich hatte Probleme mit sogenannten "Chip & Conquer" -Relationen. Hier sind einige Beispielprobleme: T(n)=T(n−5)+cn2T(n)=T(n−5)+cn2T(n) = T(n-5) + cn^2 und T(n)=T(n−2)+lognT(n)=T(n−2)+log⁡nT(n) = T(n-2) + \log{n} Ich soll eine...

Ist n !2 ! ⋅ 4 ! ⋅ 8 ! … ( N / 2 ) != O (4n)n!2!⋅4!⋅8!…(n/.2)!=Ö(4n)\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)? Ich stecke wirklich fest und glaube, dass es wahr ist, aber ich weiß nicht, wie ich es beweisen soll. Jede Hilfe wäre

Diese Frage basiert auf Hausaufgaben (ohne das eigentliche Problem zu verwenden)! Angenommen, Sie haben eine Funktion, die wie folgt beschrieben wird: f(n)∈O(2n2).f(n)∈O(2n2).f(n) \in O(2n^2) \, . Können Sie dann Folgendes behandeln: f(n)=2n2f(n)=2n2f(n) = 2n^2 und führt Mathematik darauf und...

Lösen der Wiederholungsrelation . Das Buch, aus dem dieses Beispiel stammt, behauptet fälschlicherweise, dass indem es errät und dann argumentiert T.( n ) = 2 T.( ⌊ n / 2 ⌋ ) + nT.(n)=2T.(⌊n/.2⌋)+nT(n) = 2T(\lfloor n/2 \rfloor) + nT.( n ) = O ( n )T.(n)=Ö(n)T(n) = O(n)T.( n ) ≤ c nT.(n)≤cnT(n) \leq...

Einige Autoren definieren auf eine etwas andere Weise: Verwenden für diese alternative Definition (lesen Sie „Omega Infinity“). Wir sagen, dass wenn es eine positive Konstante so dass für unendlich viele ganze Zahlen , während das übliche erfordert, dass dies für alle ganzen Zahlen gilt, die größer...

Ist es bei einem gegebenen Problem möglich zu beweisen, wie die beste Worst-Case-Effizienz eines Algorithmus zur Lösung dieses Problems wäre? Nehmen wir zum Beispiel das Problem des Sortierens eines Arrays. Viele der einfacheren Sortieralgorithmen haben eine Worst-Case-Effizienz von wie z. B. Quick...

Ich arbeite aus dem Lehrbuch CLRS-Algorithmen der 3. Auflage und in Kapitel 3 beginnt eine Diskussion über die asymptotische Notation, die mit beginnt ΘΘ\ThetaNotation. Ich habe die anfängliche Definition von verstanden:

Ich habe eine Hausaufgabe, bei der ich die Formel und die Reihenfolge von die durch gegeben istT(n)T(n)T(n) T(1)=1T(n)=T(n−1)T(n−1)+1.T(1)=1T(n)=T(n−1)T(n−1)+1.T(1) = 1 \qquad\qquad T(n) = \frac{T(n-1)}{T(n-1) + 1}\,. Ich habe festgestellt, dass aber jetzt bin ich ein wenig verwirrt. Ist die...

Der Titel der Frage drückt aus, wonach ich suche - dies soll mir helfen, die Voraussetzungen für den Satz der nichtdeterministischen Zeithierarchie besser zu verstehen Zum Beispiel erklärt das Arora-Barak-Buch den Satz mit und - aber ich kann das auch sehen! Ich versuche also besser zu verstehen,...

Es ist schon eine Weile her, dass ich eine Wiederholung lösen musste und ich wollte sicherstellen, dass ich die iterative Methode zur Lösung dieser Probleme verstehe. Gegeben: T.( n ) = 3 T.( n - 2 )T(n)=3T(n−2)T(n) = 3T(n-2) Mein erster Schritt bestand darin, Begriffe iterativ zu ersetzen, um zu...

Dies sind keine Hausaufgaben. Ich habe die Lösung, aber es ist nicht das, was ich bekomme. Ich weiß, dass es mehrere Lösungen für das Problem gibt, aber ich möchte sicherstellen, dass mir nichts entgeht. Die Frage lautet wie folgt: Man beweise, dass 2 - 4n + 7 = Θ ( ) ist. Geben Sie die Werte der...