Landau-Symbole/Komplexität: Multiplikation mit größerer Zahl

Neue Frage »

Sarah2015 Auf diesen Beitrag antworten »
Landau-Symbole/Komplexität: Multiplikation mit größerer Zahl
Meine Frage:
Ich mache gerade eine Komplexitätsrechnung.
Ich bin so weit, dass ich für eine Funktion Komplexität habe ().
Nun muss ich die für berechnen (also viele). Dabei gilt .
Ich frage mich, wie es dann mit der Komplexität aussieht.

Meine Ideen:
Meine Idee ist:

.

Stimmt das?
HAL 9000 Auf diesen Beitrag antworten »

Die Komplexität ist einfach , worin dann beide Größen in das Grenzwertverhalten einbezogen werden müssen.

Angesichts deiner Angabe mit "nach oben offenem" ist das aber nicht gleich . unglücklich

Womöglich hast du dich verschrieben und meinst stattdessen ? In dem Fall wäre zutreffend.


P.S.: Das in der Mitte der letzten Zeile ist komplett deplatziert: ist bei dir ein Index ohne jeden globale Bedeutung, besitzt also losgelöst vom Rahmen keinen Sinn.
IfindU Auf diesen Beitrag antworten »

Noch eine Warnung. Es kann sein, dass für jedes gilt , aber nicht uniform in . So könnte es auch sein, wenn man fest angenommen hat am Anfang.
Sarah2015 Auf diesen Beitrag antworten »

Sorry, das mit dem war verwirrend. Meinte es so:
Da ist, ex. ein , sodass .
Ich will die Komplexität gerne nur in Abhängigkeit von ,
daher dachte ich mir dann

Geht das nicht? unglücklich
IfindU Auf diesen Beitrag antworten »

Und was wenn ist? Dann ist .
Sarah2015 Auf diesen Beitrag antworten »

Mhm ja, danke.
Okay, dann gebe ich das mal auf, es nur i.A. von ausdrücken zu wollen.
Es ist dann also . Ich kann dann aber schon sagen, dass das mind. ist, oder?

Und wenn noch darauf addiert wird, also , kann man dann sagen, dass das in der Asymptotik nichts aus macht? Also ?
 
 
IfindU Auf diesen Beitrag antworten »

Zitat:
Original von Sarah2015
Es ist dann also . Ich kann dann aber schon sagen, dass das mind. ist, oder?

In dem Sinne, dass ist, ja.
Zitat:

Und wenn noch darauf addiert wird, also , kann man dann sagen, dass das in der Asymptotik nichts aus macht? Also ?

Stimmt.
Sarah2015 Auf diesen Beitrag antworten »

Super, danke für die Hilfe!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »