O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:56 Mi 06.05.2009 | | Autor: | farnold |
Hallo,
hier meine Definition die ich zu O-Notation habe:
f(n) = Ο(g(n)) ⇔ ∃n0 ∈ N ∧ c > 0, ∀n ≥ n0: |f(n)| ≤ c * g(n)
1.) Angenommen ich habe irgendeine Laufzeitkomplexität rekursiv gegeben durch:
T(n) = T(n-1) + O(n) darf ich dann auch c*n anstelle von O(n) schreiben? Oder c*n² statt O(n²)? Bzw. O(1) = c ?
2.) Nur anhand von T(n) = T(n-1) + O(n) kann ich nicht sagen wie der nächste Rekursionsschritt aussehen wird, oder?
z.B T(n) = T(n-2) + O(n) + O(n-1) ist nicht ungebdingt richtig!
Das kann ich nur anhand von z.B dem Quellcode erkennen, wie es weitergeht und meine Vermutung muss ich dann durch Induktion beweise?
3.) Betrachten wir O(n²). Wäre laut obiger Definition das "g(n)" = n² und f(n) wäre eine Funktion kleinergleich c*g(n) = c*n²?
4.) angenommen es ist die Laufzeitkomplexität f(n) = 4n² + 3n + 117, wenn ich nun zeigen soll, dass f(n) in O(n²) liegt muss ich doch nur zeigen dass es ein c gibt für das ab einem gewissen Wert gilt: f(n) <=(kleinergleich) c*n², oder?
wäre super, wenn ihr die Fragen mit ja/nein beanwortet, damit ich sehen kann, ob meine Vorstellung von der O-Notation richtig ist.
mfg fa
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 19:39 Do 07.05.2009 | | Autor: | farnold |
Ich bin immernoch an Hilfe interessiert und sehr dankbar :)
die klausur naht mit großen schritten und da wollte ich die letzten unklarheiten noch beseitigen.
eine neue frage hat sich mir noch gestellt:
in unserem Skript steht dass O(n) den WorstCase beschreibt.
wird der worst, best, averagecase nicht beim Aufstellen der Laufzeitkomplexität T(n) festgelegt und bei O(n) betrachte ich die obere Schranke des best, worst, averagecases? => O(n) beschreibt nicht unbedingt den worstcase!?
grüße fa
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Sa 09.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Fr 08.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
