 Laufzeit |
Physiker
unregistriert
 |
|
Meine Frage:
Hallo zusammen,
ich habe eine Frage zur Definition der Laufzeit von Algorithmen. Und zwar, inwiefern das Vorhandensein von Ressourcen dabei berücksichtigt wird. Ich weiß nicht genau, wie ich es ausdrücken soll, aber hier ein Beispiel:
Ein riesiger Supercomputer rechnet natürlich schneller als mein PC zu Hause.
Meine Ideen:
Wenn man jetzt die Landau-Notation hernimmt, wäre das natürlich kein Problem. Man gibt ja nur die Größenordnung an und muss im Nachhinein einen computerspezifischen Faktor berücksichtigen. Mein Problem ist: Ich habe einen Algorithmus entwickelt, der nicht auf einem Computer läuft, sondern ein eigenes Gerät braucht. Das Problem ist jetzt, dass wenn ich meine betreffende Variable n, die die Laufzeit bestimmt, verdoppeln will, MUSS ich mein Gerät größer bauen, und zwar genau verdoppeln; wenn ich das jedoch mache, ändert sich an der Laufzeit ÜBERHAUPT NICHTS... Ist dass jetzt eine Laufzeit O(n) (Verdopplung der Variable n erfordert eine Verdopplung der Ressourcen) oder eine Laufzeit von O(1), womit ich konstant meine... ???
Ist eine ziemlich seltsame Frage und ich weiß auch nicht, ob ich den Kern des Themas überhaupt schon verstanden habe.
Im Voraus schon Danke für euere Hilfe!
|
|
28.07.2011 21:14 |
|
|
nattydread
Grünschnabel
Dabei seit: 28.07.2011
Beiträge: 9
|
|
das versteh ich nicht so ganz...vllt könntest du uns den algorithmus und deine maschine etwas näher beschreiben
|
|
|
29.07.2011 19:13 |
|
|
Physiker
unregistriert
|
|
Ist geheim und würde außerdem eh nichts bringen. Das Problem ist sehr abstrakt 
|
|
|
29.07.2011 19:33 |
|
|
nattydread
Grünschnabel
Dabei seit: 28.07.2011
Beiträge: 9
|
|
ok...also nun folgende frage: bleibt deine laufzeit konstant wenn du n verdoppelst UND die größe deiner maschine verdoppelst?
es ist immer ziemlich schwierig die laufzeit eines algorithmus zu bestimmen ohne diesen direkt zu kennen 
|
|
|
29.07.2011 19:41 |
|
|
Physiker
unregistriert
|
|
Danke dass du es versuchst!
Ja, wenn ich die Größe der Maschine verdoppele und n verdoppele, bleibt die Laufzeit konstant.
|
|
|
29.07.2011 22:28 |
|
|
nattydread
Grünschnabel
Dabei seit: 28.07.2011
Beiträge: 9
|
|
dann ist die laufzeit O(n)...im normalfall,wenn du n verdoppelst...aber die rechenkapazität gleich bleibt...würde sich die laufzeit auch verdoppeln...
wenn du aber die rechenkapazität verdoppelst..bleibt ja dann bei doppelten n die laufzeit konstant
|
|
|
29.07.2011 22:39 |
|
|
Physiker
unregistriert
|
|
Das lustige ist: die "Laufzeit" als Zeit die die Maschine zum berechnen braucht verdoppelt sich nicht zwingend, wenn ich n verdopple. Sie kann sich verdoppeln, aber auch gleichbleiben.
Ich glaube, es hat keinen Sinn so. Mein Algorithmus ist ZIEMLICH seltsam. Ich hab noch ein paar andere Quellen eingeholt und denke jetzt, dass man es, wie du auch sagst, als eine Entartung einer linearen Entwicklung darstellen.
Danke dir! 
|
|
|
29.07.2011 23:27 |
|
|
|
