In welche große O-Klasse würde die Funktion (1/2)^n fallen?Große O-Klasse für (1/2)^n
Auf einer rein mathematischen Basis scheint es so, als müssten wir es in O (1) schreiben, weil 1/2^n für jedes ausreichend große n 0 ist.
Wenn es jedoch um asymptotische Analyse und Big O geht, tendieren wir dazu, viel Hand-Winken zu machen und auch auf Formeln zurückzugreifen. 1/2 ist technisch eine Konstante, so würde scheinbar in O (c^n) fallen.
Ich lehne mich nach O (c^n), weil das Sagen von "halber Operation" keinen Sinn macht, wenn man von Algorithmen spricht. Welcher Algorithmus benötigt die Hälfte der Zeit, wenn die Eingabe größer wird? Im besten Fall sehe ich die mathematische Formel (1/2)^n, die sich auf die Hälfte einer Zeitkonstante bezieht - etwa eine Minute. Also (30 Sekunden) wird^n zu einer großen Zahl und die Funktion gehört eindeutig in O (c^n).
Ein wenig Hilfe?
Abnehmende Funktionen werden in der Laufzeit-/Raumkostenanalyse nicht häufig verwendet, aber Sie sehen sie ständig in der Analyse numerischer Fehler. Da ist der Unterschied zwischen 1 und 1/n und 1/2^n wirklich wichtig. Natürlich ist 1/n trivialerweise O (1), da Big-O wie <= ist. Vielleicht wollten Sie stattdessen nach Big-Theta fragen? –
Ich versuche, eine Reihe von mathematischen Funktionen in der Reihenfolge von der kleinsten Reihenfolge des Wachstums bis zum höchsten zu platzieren. Die obige Funktion ist eine davon. Und ich versuche herauszufinden, ob es darunter gehört, sagen wir O (logn) oder darüber, sagen wir O (n^3). – zzu
So sicher, funktioniert Big Theta ... was Big Theta Klasse ist (1/2)^n in? – zzu