Wachstumsordnungen Frage Klausur B WS 07/08

Moderator: Moderatoren

Antworten
Benutzeravatar
beafraid88
Beiträge: 99
Registriert: Sa 25. Okt 2008, 17:34
Wohnort: Aachen/Düsseldorf/Mönchengladbach

Wachstumsordnungen Frage Klausur B WS 07/08

Beitrag von beafraid88 » Do 17. Feb 2011, 17:50

hey leute,


könnt ihr mir sagen, warum bei aufg. 1b)

n*log2(n) ε O(n)

und

log2(n)*log2 ε O(log2(n)) ist?

log2 ist doch größer 1 für n--> unendlich ...

ulrich
Beiträge: 3
Registriert: So 28. Nov 2010, 21:01
Wohnort: Neuss

Re: Wachstumsordnungen Frage Klausur B WS 07/08

Beitrag von ulrich » Sa 19. Feb 2011, 00:56

(1)
n*log2(n) ε O(n) ist falsch.

(2)
log2(n)*log2 ε O(log2(n))
Das steht da nicht. Da steht:
log2 (log2 (n)) ist Element von O(log2 n)
log(x) wächst langsamer als x. (Ersetze dann x durch log2(n) und du siehst, dass die Aussage richtig ist.

delmari
Beiträge: 3
Registriert: Sa 19. Feb 2011, 00:19

Re: Wachstumsordnungen Frage Klausur B WS 07/08

Beitrag von delmari » Sa 19. Feb 2011, 09:07

hallo
was denn O(n*log2(n))

Antworten

Zurück zu „Info I“