o (n log(n)) |
| 12.08.2013, 14:22 | olivia und patrick | Auf diesen Beitrag antworten » |
| o (n log(n)) Hallo Zusammen Ich stehe vor folgender Aufgabe: O-Verhalten (Laufzeit) Sei: f(n) = n Beweisen Sie: O(f(n)) = O(n*log(n)) Meine Ideen: Unserer Meinung nach kann das nicht sein, weil f(n) = n doch linear ist und O(f(n)) = O(n*log(n)) nicht. Allerding ist nicht die Aufgabenstellung zu entscheiden ob richtig oder falsch und dies zu begründen, sondern nur, zu beweisen, das es so ist. Kann uns jemand einen Ansatz geben? Vielen Dank für eure Hilfe!! |
||
| 12.08.2013, 17:16 | Optimizer | Auf diesen Beitrag antworten » |
Diese Gleichheit ist ja eigentlich eine Mengengleichheit. Schreibe erstmal die entsprechenden Mengen aus. Dannach: Eine Menge ist eine Teilmenge der anderen (welche?). Um dann zu zeigen, dass die Mengen nicht gleich sind, nimm ein Element aus der "größeren" Menge heraus und zeige, dass es nicht in der kleineren Menge ist. |
||
|
|