Frage zur O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:13 So 10.11.2013 | | Autor: | IncepTer |
Hallo Freunde,
ich habe eine Frage zu der O-Notation, speziell zu einer Aufgabe.
Der Grundgedanke, der dahinter steckt, ist mir ja soweit klar, aber wie unser Prof. manche Aufgaben "löst" ist mir eher schleierhaft.
Z.B.: 5n²-3n+1 [mm] \in [/mm] O(n²)
Ergebnis: 5n² + 0 + n² [mm] \le [/mm] 6n² [mm] \in [/mm] O(n²)
Was macht er mit der -3n und wieso wird das 0?
Ich weiß ja, dass bei einer Division/Mult. mit einer negativen Zahl sich das Zeichen umkehrt. Aber hier findet doch keine Divsion/Mult. statt?
Bitte um Aufklärung :P
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Hallo Freunde,
>
> ich habe eine Frage zu der O-Notation, speziell zu einer
> Aufgabe.
> Der Grundgedanke, der dahinter steckt, ist mir ja soweit
> klar, aber wie unser Prof. manche Aufgaben "löst" ist mir
> eher schleierhaft.
>
> Z.B.: 5n²-3n+1 [mm]\in[/mm] O(n²)
>
> Ergebnis: 5n² + 0 + n² [mm]\le[/mm] 6n² [mm]\in[/mm] O(n²)
>
> Was macht er mit der -3n und wieso wird das 0?
> Ich weiß ja, dass bei einer Division/Mult. mit einer
> negativen Zahl sich das Zeichen umkehrt. Aber hier findet
> doch keine Divsion/Mult. statt?
Das Ziel ist eine obere Schranke zu finden.
In deinem Fall gilt: Die Komplexität eines Polynoms ist die der höchsten vorkommenden Potenz.
In deiner Aufgabe wurde einfach nach oben abgeschätzt.
Sieh dir dazu mal die Rechenregeln zur O-Notation an.
Valerie
|
|
|
|
