Groß-O-Notation mit Log < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:43 Do 21.03.2013 | | Autor: | DerIcke |
| Aufgabe | Nennen Sie die Groß-O-Notation der rekurrenten Relation
3T(n/2) + 4T(n/4) + n log n |
Hallo, ich weiß erst einmal Folgendes:
3T(n/2) + 4T(n/4) + n log n < 3T(n/2) + 4T(n/2) + n log n
= 7T(n/2) + n log n
Nach dem Master-Theorem ist a = 7, b = 2 und c...ja...was ist c? [mm] (n^c)
[/mm]
Kann mir da jemand auf die Sprünge helfen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
> Nennen Sie die Groß-O-Notation der rekurrenten Relation
> 3T(n/2) + 4T(n/4) + n log n
> Hallo, ich weiß erst einmal Folgendes:
>
> 3T(n/2) + 4T(n/4) + n log n < 3T(n/2) + 4T(n/2) + n log n
>
> = 7T(n/2) + n log n
>
> Nach dem Master-Theorem ist a = 7, b = 2 und c...ja...was
> ist c? [mm](n^c)[/mm]
> Kann mir da jemand auf die Sprünge helfen?
Naja, $n [mm] \log(n)$ [/mm] entspricht KEINEM [mm] $n^c$ [/mm] exakt.
Aber schau' mal hier: ![[]](/images/popup.gif) Wiki
da wird sowas ähnliches gelöst.
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 01:18 Do 21.03.2013 | | Autor: | DerIcke |
Danke für die super schnelle Antwort. Der Wikipedia-Artikel ist allerdings recht komplex formuliert. Wäre es möglich, dass du oder jemand Anders, dies nochmal anders ausformuliert, bzw. an meine Aufgabe anlehnt?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 Sa 23.03.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
