Informatik2 Aufgabensammlung 1.0.pdf

Exams
Uploaded by Anonymous User at 2019-02-09
Description:

Umfassende Aufgabensammlung nach Themenbereichen sortiert

 0
105
6
Download
f1 < f2 < f5 < f4 < f3 < f6 ?
View 6 more comments
f5(n) = n*sqrt(n/2) = sqrt(n^2)*sqrt(n/2) = sqrt(n^2 * n/2) = (n^2 * n/2)^(1/2) = ((n^3)/2)^(1/2). Das ist n^(3/2)/sqrt(2), also in O(n^(3/2)). Einfacher sieht man f5 < f2 aber einfach durch n*sqrt(n) < n*n
Genau das
Lösung?: f9 < f5 < f8 < f10 < f7 < f3 < f1 < f2 < f4 < f6
View 4 more comments
f9 < f5 < f8 < f7 < f10 < f3 < f1 < f2 < f4 < f6 muss es nicht so heißen? Weil bei f7 ist doch ein plus das bedeutet doch 2log2n ist doch kleiner als 2^logn
f7 und f10 sind gleich. Das 2log(n) wächst deutlich langsamer als das n^(1/3), weshalb man das einfach weglassen kann. Formal zeigen kann man das so: n^(1/3)+2log2(n) < n^(1/3)+n^(1/3) = 2*n^(1/3) in O(n^(1/3)) für große n. f10 ist ebenfalls in O(n^(1/3)), weil 2^(log8(n)) = 2^(log2(n) / log2(8)) = (2^(log2(n)))^(1/log2(8)) = n^(1/log2(8)) = n^(1/3)
f1 < f2 < f5 < f4 < f9 < f8 < f7 < f3 < f6 ?
Habe es auch so
f4 < f1 < f3 < f2 < f6 < f7 < f5 ? wobei f1 = f3
Hat das jemand schon gemacht
Hat bereits jemand korrekte Lösungen zu den Aufgaben und wäre bereit, diese hochzuladen ? Danke :)