Laufzeit Alogrithmen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:53 Sa 07.01.2017 | | Autor: | Franhu |
| Aufgabe | Ab welcher Input-Grösse (Anzahl Datenelemente) ist Algorithmus a schneller als Algorithmus b?
Algorithmus a: T(10'000) = 400ms und f(n) = [mm] n^2
[/mm]
Algorithmus b: T(10'000) = 240ms und f(n) = n * log(n) |
Hallo Zusammen
Für die Berechnung von der Laufzeit kenne ich folgende Formel:
[mm] \bruch{T(n)}{T(n_{1})} [/mm] = [mm] \bruch{f(n)}{f(n_{1})}
[/mm]
Damit kann ich zum Beispiel die Laufzeit für Alogrithmus a bei n = 100'000 Elementen berechnen.
Ich möchte nun wissen, ab welcher Menge n Algorithmus a von Algorithmus b überholt wird. Wie muss ich die Gleichung gleichsetzen, ich steh grad voll auf der Leitung.
Danke für eure Hife.
Lg Franhu
|
|
| |
|
Hallo,
> Ab welcher Input-Grösse (Anzahl Datenelemente) ist
> Algorithmus a schneller als Algorithmus b?
> Algorithmus a: T(10'000) = 400ms und f(n) = [mm]n^2[/mm]
> Algorithmus b: T(10'000) = 240ms und f(n) = n * log(n)
> Hallo Zusammen
>
> Für die Berechnung von der Laufzeit kenne ich folgende
> Formel:
>
> [mm]\bruch{T(n)}{T(n_{1})}[/mm] = [mm]\bruch{f(n)}{f(n_{1})}[/mm]
>
> Damit kann ich zum Beispiel die Laufzeit für Alogrithmus a
> bei n = 100'000 Elementen berechnen.
>
Über die Gültigkeit der Formel kann ich dir ad hoc gerade nichts sagen (gehen wir davon aus, dass sie stimmt). Was muss dann für den Quotienten
[mm] \frac{f(n)}{f(n_1)}[/mm]
gelten, wenn bspw. f(n) [mm] \supset f(n_1) [/mm] ist? Dabei wäre eigentlich nur noch zu beachten, dass alle beteiligten Werte hier offensichtlich positiv sind.
> Ich möchte nun wissen, ab welcher Menge n Algorithmus a
> von Algorithmus b überholt wird. Wie muss ich die
> Gleichung gleichsetzen, ich steh grad voll auf der
> Leitung.
Betrachte es nicht als Gleichung, sondern als Ungleichung.
Gruß, Diophant
|
|
|
| |
|
> Ab welcher Input-Grösse (Anzahl Datenelemente) ist
> Algorithmus a schneller als Algorithmus b?
> Algorithmus a: T(10'000) = 400ms und f(n) = [mm]n^2[/mm]
> Algorithmus b: T(10'000) = 240ms und f(n) = n * log(n)
> Hallo Zusammen
>
> Für die Berechnung von der Laufzeit kenne ich folgende
> Formel:
>
> [mm]\bruch{T(n)}{T(n_{1})}[/mm] = [mm]\bruch{f(n)}{f(n_{1})}[/mm]
>
> Damit kann ich zum Beispiel die Laufzeit für Alogrithmus a
> bei n = 100'000 Elementen berechnen.
[mm]\bruch{T_a(n)}{T_a(n_{1})}[/mm] = [mm]\bruch{f_a(n)}{f_a(n_{1})}[/mm] sowie [mm]\bruch{T_b(n)}{T_b(n_{1})}[/mm] = [mm]\bruch{f_b(n)}{f_b(n_{1})}[/mm] mit [mm] n_1=10.000.
[/mm]
Dabei soll n die gesuchte Anzahl sein, bei der [mm] T_a(n)=T_b(n) [/mm] wird.
Also:[mm]T_a(n)=T_a(n_{1})*\bruch{f_a(n)}{f_a(n_{1})}[/mm] sowie [mm]T_b(n)=T_b(n_{1})*\bruch{f_b(n)}{f_b(n_{1})}[/mm] mit [mm] n_1=10.000 [/mm] und .
[mm] T_a(n)=T_b(n), [/mm] also [mm]T_a(n_{1})*\bruch{f_a(n)}{f_a(n_{1})}[/mm] = [mm]T_b(n_{1})*\bruch{f_b(n)}{f_b(n_{1})}[/mm]
[mm]400*\bruch{n^2}{10.000^2}[/mm] = [mm]240*\bruch{n*ln(n)}{10.000*ln(10.000)}[/mm]
[mm]\bruch{400*ln(10.000)}{240*10.000}[/mm] = [mm]\bruch{ln(n)}{n}[/mm]
Als Näherungslösung (Intervallschachtelung, Newtonsches Näherungsverfahren...) erhältst du für n ungefähr den Wert 1, d.h., nur unter 1 (also: gar nicht) ist a schneller als b.
|
|
|
|
