was bedeutet 'polynomiell in n'?

Question

Frage:

was bedeutet 'polynomiell in n' ? nur O(n) oder kann auch sein, O(n^k) fuer k > 1 ?

Answer 1

Die Laufzeit \(f(n)\) eine Algorithmus ist polynomiell in \(n\), wenn es ein \(k\in \mathbb{N}\) gibt, so dass

        \(f(n)\in O(n^k)\)

ist.

Answer 2

Passt "gross O" oder "Landau-Symbol" zu eurer Definition des fraglichen Begriffs?

https://de.wikipedia.org/wiki/Landau-Symbole

Comments

ja, + ich soll eine algorithmus schreiben, und sie haben gesagt, "Die Laufzeit des Algorithmus sollte
polynomiell in n sein"

---

Tipp für deine weitere Suche: https://www.stacklounge.de/6361/folgende-sprache-polynomialzeit-entscheidbar-palindrom?state=showcomments-6361&show=6361#q6361 .