O-Notation < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:36 Do 08.07.2010 | | Autor: | Torboe |
| Aufgabe | Gegeben seien die Funktionen:
[mm] f_{1}(n) [/mm] = [mm] log_{2}(\wurzel{n} [/mm] * n),
[mm] f_{2}(n) [/mm] = [mm] \wurzel{n} [/mm] * [mm] log_{2}(n),
[/mm]
[mm] f_{3}(n) [/mm] = [mm] log_{2}({\wurzel{n^{3}}})
[/mm]
Für welche (i,j), i =/ j, gilt fi = O(fj)? |
hey zusammen,
ich habe gehört, dass man nicht alle funktionen miteinander vergleichen muss. sondern dass es reicht, sie nach der größe zu ordnen und dann die erste mit der zweiten, die zweite mit der dritten, usw zu vergleichen?!
also:
f2(n) > f1(n) = f3(n)
[mm] \limes_{n\rightarrow\infty} \bruch{\wurzel{n} * log_{2}(n)}{log_{2}(\wurzel{n} * n)} [/mm] = [mm] \bruch{n^{1/2}*log_{2}(n)}{3/2 * log_{2}(n)} [/mm] = [mm] \bruch{n^{1/2}}{3/2} [/mm] = [mm] \infty
[/mm]
=> f1(n) = O(f2(n))
und beim vergleichen von f1(n) mit f3(n) folgt:
da beide ja gleich sind, ist der limes von beiden 1, also ein fester wert und daraus folgt:
=> f1(n) = O(f3(n)), f3(n) = O(f1(n))
muss dann f2 und f3 noch verglichen werden oder ist das so ausreichend?
danke schonmal im voraus!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:22 Mi 14.07.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
