Zu welchen Algorithmen gibt es Beweise, dass es keine bessere worst-case Komplexität für das jeweilige Problem geben kann, als jener Algorithmus?
Einfacher gesagt: Für welche Algorithmen gibt es Beweise, dass sie der jeweils bestmögliche Algorithmus für das Problem sind und dass es keinen besseren Algorithmus geben kann?
Man kann noch zeigen, dass eine 1-Band-TM für die Sprachen
[latex]\{ww\mid w\in\{0,1\}^*\},~\{ww^R\mid w\in \{0,1\}^*\}[/latex] mindestens [latex]\Omega(n^2)[/latex]
Zeit benötigt. Und zwar geht das mithilfe von Kolmogoroff-Komplexität.
Ansonsten sind alle mir bekannten Sprachen, für die ein Mindestmaß
an Platz/Zeit gezeigt werden kann, mit Diagonalisierung konstruiert.
Zu welchen Algorithmen gibt es Beweise, dass es keine bessere worst-case Komplexität für das jeweilige Problem geben kann, als jener Algorithmus?
Einfacher gesagt: Für welche Algorithmen gibt es Beweise, dass sie der jeweils bestmögliche Algorithmus für das Problem sind und dass es keinen besseren Algorithmus geben kann?
Diese Frage ist irgendwie viel zu allgemein gestellt.
Beispiel:
Das Problem "Sortieren" [da fehlt dann noch etwas wie: von n Objekten einer linear geordneten Menge.]
Das geht mit sequentiellen Algorithmen sicherlich nicht besser als mit parallelen oder verteilten,
jedoch hinsichtlich welcher Bewertungsgröße denn?
Welches Komplexitätsmaß ist gemeint?
Platz, sequentielle Zeit, parallele Zeit , Work=Gesamtzahl aller (verteilten/parallelen/unabhängen) Schritte, Nachrichtenkomplexität, usw.
Da sind Aussagen wie die, die Georg machte wohl die besten, die man kriegen kann.
Letztere bezieht sich dann auf sequentielle Verfahren (Turing-Maschine)
Also nur das Problem und dann die Frage nach unterer Schranke für jedweden Algorithmus,
ist relativ schwer zu beantworten.
Das Problem und dann eine eingeschränktere Klasse von möglichen Algorithmen-Techniken,
geht vielleicht grad noch.
Für welche Algorithmen gibt es Beweise, dass sie der jeweils bestmögliche Algorithmus für das Problem sind und dass es keinen besseren Algorithmus geben kann?
Suche in einer unsortierten Liste ist im schlechtesten Fall O(n), weil das gesuchte Element ganz am Ende (oder sogar gar nicht drin) stehen kann. Ist das Beweis genug?
Diese Frage ist irgendwie viel zu allgemein gestellt.
Beispiel:
Das Problem "Sortieren" [da fehlt dann noch etwas wie: von n Objekten einer linear geordneten Menge.]
Das geht mit sequentiellen Algorithmen sicherlich nicht besser als mit parallelen oder verteilten,
jedoch hinsichtlich welcher Bewertungsgröße denn?
Welches Komplexitätsmaß ist gemeint?
Platz, sequentielle Zeit, parallele Zeit , Work=Gesamtzahl aller (verteilten/parallelen/unabhängen) Schritte, Nachrichtenkomplexität, usw.
Stimmt, das habe ich mit der Frage implizit angenommen, weil mir klar war, was ich wollte ;)
Also, es geht mir um einen normalen Einprozessorrechner, also alles sequentiell und um Zeitkomplexität.
Dankeschön!
