Ich überarbeite die formalen Definitionen von Big O und den anderen damit verbundenen Grenzen und etwas stolpert über mich. In dem Buch, das ich lese (Skiena), ist Big O definiert als:

f (n) = O (g (n)), wenn es eine Konstante c gibt, so dass f (n) für einen bestimmten Wert von n> n0 immer <= c * g (n) ist

Das macht in der Regel Sinn für mich. Wir beschäftigen uns nur mit Werten von n, die groß genug sind, damit die Wachstumsraten tatsächlich eine Rolle spielen. Aber warum g (n) mit c multiplizieren? Es scheint, als könnte ich einen sehr großen Wert für c wählen und das Ganze willkürlich machen, indem ich die Größe kleinerer g (n) -Werte herausblase.

Nebensächliche Frage: Wenn Sie einen Algorithmus in eine Komplexitätsklasse einteilen, ist es die allgemeine Faustregel, nur die niedrigste Wachstumsklasse zu wählen, die nach der Definition von Big O noch gültig ist? Gemäß der Definition scheint es gültig zu sein, einen Algorithmus mit konstanter Zeit als O (n!) Zu klassifizieren, einfach weil f (n) <= c * g (n) ist. Natürlich bietet dies keinen Wert.

Vielen Dank