-3
A (N) = Θ (N) Lassen
B (N) = Θ (N) und
C (N) = Ω (N)
Dann Was gesagt werden kann, C (N) + A (N) · B (N) & rarr;
A
Antwort
2
Sie können zeigen, dass D (n) = C (n) + A (n) * B (n) ist Ω (n^2) - dies folgt (fast) unmittelbar aus den Definitionen der Komplexitätsklassen. Sie können in der Art einer Obergrenze keine Komplexität zeigen, da C (N) so komplex sein kann wie Sie. Um genauer zu sein: Sei n_A und n_B so, dass für n> n_A gilt A (n)> k_A * n und für n> n_B gilt B (n)> k_B * n. Diese existieren, da A und B insbesondere Ω (n) sind. Wenn C (n) nicht negativ ist, gilt für n> max (n_A, n_B): C (n) + A (n) * B (n)> A (n) * B (n)> k_A * n * k_b * n = (k_A * k_B) * n^2. Mit k_D = (k_A * k_B) haben wir gefunden, dass D (n) die Bedingung erfüllt, Ω (n^2) zu sein.
Verwandte Themen
- 1. Wie löst man die Wiederholung A (n) = A (n-1) + n * log (n)?
- 2. Was ist die zeitliche Komplexität von T (n) = (T (n-1) + n!)?
- 3. Prolog: Einfaches DCG a^n b^n
- 4. Prolog Parse Tree a^n b^n
- 5. Ist die zeitliche Komplexität dieses Algorithmus O (N^2)?
- 6. Asymptotic Komplexität von T (n) = T (n-1) + 1/n
- 7. Was ist die beste Komplexität von N-Queens Puzzle?
- 8. Ist die zeitliche Komplexität dieser Funktion O (N)?
- 9. Wie ist die zeitliche Komplexität des folgenden Codes O (n)?
- 10. Komplexität von T (n) = T (cn) + T ((1-c) n)
- 11. Lösen der Matrixgleichung A B = C mit B (n * 1) und C (n * 1)
- 12. Zeitkomplexität eines Algorithmus - n oder n * n?
- 13. Übereinstimmen mit einem^n b^n c^n (z. B. "aaabbbccc") mit regulären Ausdrücken in C#
- 14. Ändern Komplexität von O (n) bis O (log n)
- 15. Sortierung von nicht sortierbaren Daten mit n log n Komplexität
- 16. Solving a Recurrence Beziehung T (n) = T (n-√n) +1
- 17. N von N Matrixdiagonalunterschied
- 18. Überlauf: a * a mod n
- 19. Rails - escape_javascript ohne all \ n \ n \ n \ n \ n
- 20. C++ Programm die Anzahl der Strings w der Länge zu berechnen, n über {a, b, c}
- 21. Wie berechnet man die zeitliche Komplexität?
- 22. Finden Sie die Komplexität der folgenden Wiederholung: T (n) = T (n/2) + log (n)
- 23. Was ist die zeitliche Komplexität dieser Lösung O (N) oder O (LogN)?
- 24. Was ist die zeitliche Komplexität meiner Funktion?
- 25. Warum ist die Komplexität von Karatsuba O (n^2) nicht?
- 26. Was wäre die zeitliche Komplexität und warum?
- 27. COINCHANGE: Dynamische Programmierung O (N) Komplexität
- 28. Was ist die zeitliche Komplexität dieser Funktion?
- 29. Was ist die zeitliche Komplexität des folgenden Programms? Ist O (log n) korrekt?
- 30. Was bedeutet "const char (& a) [N]"?
Können Sie ein wenig weiterarbeiten? –
@ JonSillick: Da gehst du. Aber wirklich, Sie sollten ein grundlegendes Lehrbuch über Algorithmen oder Programmier-und-Algorithmen lesen, wo Sie eine Behandlung dieses Themas und wahrscheinlich ein paar Übungen finden werden. Ich nehme an, du bist ein Student oder Gymnasiast - also kannst du auch einfach deinen Lehrer oder TA bitten, dir dabei zu helfen. – einpoklum
@JonSillick Ich denke, du musst deine Frage ausarbeiten, wenn du willst, dass die Leute ihre Antworten ausarbeiten. –