O-Notation Beweisen Sie (n+1)! = O(n!)
-
Steht da wirklich ein Gleichheitszeichen?
-
Naja, wird wohl oft so geschrieben, auch wenns eigentlich eher ein sein sollt...
-
Wollen die jetzt wirklich nen Beweis
Was hast du an "Beweisen oder widerlegen sie" nicht verstanden? Mir fallen spontan 2 bis 3 (wahrscheinlich nicht) verschiedene Moeglichkeiten ein, das zu widerlegen.
Was ist so problematisch einfach die Definition zu verwenden http://de.wikipedia.org/wiki/Landau-Symbole und einzusetzen? Ausrechnen und ueberpruefen, ob es eine wahre Aussage ist?
-
adonis schrieb:
Wollen die jetzt wirklich nen Beweis, wenn ja wie gehe ich den an?
Ich würde mich aufs Widerlegen konzentrieren.
-
Ich hab nur gefragt, weil die Aufgabe eben so leicht wäre, wenn da ein Element von stünde, dass ich mir vorstellen könnte, dass es sich um eine formale Spitzfindigkeitsaufgabe handelt.
-
Ja soll ∈ sein, ist halt der kurs datenstrukturen algorithmen.
reicht hier die Grenzwertbetrachtung?Und wie fest sind die diese laufzeitklassen?
Ich würde sagen (n+1)! = n! ist nicht richtig und müsste
eher O(n+1)! sein
-
Über die Grenzwertdefinition ist es wohl am einfachsten zu widerlegen, ja.
-
Aber wie sieht es mit diesen klassen aus? soll ich dafür außer acht lassen.
Weil wenn ich die betrachte gibts c^n n! n^n usw.dann könnte es ja nur n! sein.
alles sehr verwirrend.
-
Du sollst doch nur zeigen, dass (n+1)! nicht in O(n!) liegt.
-
Also wenn du zeigen kannst das:
lim f(n)/g(n) nicht über alle Maßen steigt, stimmt die Aussage, sonst nicht.
mit f=O(g)
also lim ((n+1)!/n!)
