AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Delphi-PRAXiS - Lounge Klatsch und Tratsch Konstante für Komplexitätsklasse finden

Konstante für Komplexitätsklasse finden

Ein Thema von Angel4585 · begonnen am 24. Jan 2012 · letzter Beitrag vom 24. Jan 2012
Antwort Antwort
Angel4585

Registriert seit: 4. Okt 2005
Ort: i.d.N.v. Freiburg im Breisgau
2.199 Beiträge
 
Delphi 2010 Professional
 
#1

Konstante für Komplexitätsklasse finden

  Alt 24. Jan 2012, 13:29
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

Kann mir da jemand auf die Sprünge helfen?
Martin Weber
Ich bin ein Rüsselmops

Geändert von Angel4585 (24. Jan 2012 um 13:58 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von s.h.a.r.k
s.h.a.r.k

Registriert seit: 26. Mai 2004
3.159 Beiträge
 
#2

AW: Ganz schön komplex

  Alt 24. Jan 2012, 13:39
Kannst du deinem Thread mal einen Aussagekräftigen Titel geben?! Wäre nett, danke

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!?
»Remember, the future maintainer is the person you should be writing code for, not the compiler.« (Nick Hodges)

Geändert von s.h.a.r.k (24. Jan 2012 um 13:47 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Gausi
Gausi

Registriert seit: 17. Jul 2005
647 Beiträge
 
RAD-Studio 2009 Pro
 
#3

AW: Ganz schön komplex

  Alt 24. Jan 2012, 13:54
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)
The angels have the phone box.
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#4

AW: Konstante für Komplexitätsklasse finden

  Alt 24. Jan 2012, 14:21
n^2 is doch wohl o(2^n). Also kannst Du jeden beliebigen positiven Wert > 0 nehmen.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 00:16 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf