Delphi-PRAXiS

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Klatsch und Tratsch (https://www.delphipraxis.net/34-klatsch-und-tratsch/)
-   -   Konstante für Komplexitätsklasse finden (https://www.delphipraxis.net/165969-konstante-fuer-komplexitaetsklasse-finden.html)

Angel4585 24. Jan 2012 13:29


Konstante für Komplexitätsklasse finden
 
Hallöchen :)

Ich bereite mich grad auf meine Klausuren vor und arbeite die alten Klausuren durch bei denen ich ein Problem bei einer Aufgabe habe.

Wir sollen beweisen, dass etwas innerhalb einer bestimmten Komplexität liegt indem wir eine Konstante berechnen, also z.B.:

3n² + 2n + 5 = O(n²)
3n² + 2n + 5 <= 3n² + 2n² + 5n²
3n² + 2n + 5 <= 10n²

=> Die gesuchte Konstante ist 10.

Die Aufgabe bei der ich Probleme habe ist folgende:

n² = O(2^n) (also 2 hoch n)

Ich hab keinen Plan wie ich da anfange :oops:

Kann mir da jemand auf die Sprünge helfen? :cyclops:

s.h.a.r.k 24. Jan 2012 13:39

AW: Ganz schön komplex
 
Kannst du deinem Thread mal einen Aussagekräftigen Titel geben?! Wäre nett, danke :thumb:

Ich würde hier so anfangen:

n^2 = O(2^n)
n^2 <= a*2^n

So kommst ja auf die Konstante. Soweit ich das noch weiß geht es ja darum, dass du eine Konstante findest, aber der das eben gilt, oder? Dann dürfte der Ansatz doch passen!?

Gausi 24. Jan 2012 13:54

AW: Ganz schön komplex
 
Naja, eine Konstante ist 1, und für n >= 4 gilt

Code:
n^2 <= 2^n
Das würde ich einfach per Induktion zeigen. Der Induktionsanfang ist klar: 4^2=16 und 2^4=16, stimmt also.

Induktionsschritt n -> n+1:
Code:
   (n+1)^2 
= n^2 + 2n + 1 
<= n^2 + 2n + 2n   (n >= 4)
= n^2 + 4n
<= n^2 + n^2        (n >= 4)
<= 2 * 2^n         (Induktionsvoraussetzung)
= 2^(n+1)
Somit liegt n^2 in O(2^n)

gammatester 24. Jan 2012 14:21

AW: Konstante für Komplexitätsklasse finden
 
n^2 is doch wohl o(2^n). Also kannst Du jeden beliebigen positiven Wert > 0 nehmen.


Alle Zeitangaben in WEZ +1. Es ist jetzt 13:08 Uhr.

Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz