Sortieralgorithmen

[MEL]

a)
Wie groß muss eine sortierte Liste sein, um bei einer rekursiven linearen Suche
innerhalb der Liste eventuell einen Stapelüberlauf der Python-Virtuelle-
Maschine zu produzieren?
b)
Wie groß kann eine sortierte Liste maximal sein, bevor bei einer rekursiven
Binärsuche ein Stapelüberlauf verursacht wird?
Erläutern Sie beide Antworten.


weiß jemand die antworte von diese aufgabe

[/me]

weiß jemand die antworte von diese aufgabe

Ein erster Ansatzpunkt könnte sys.getrecursionlimit sein.

Der genaue Wert hängt vom verwendeten Python-Interpreter ab (CPython 2.7 und PyPy 1.9 liefern mir deutlich unterschiedliche Werte) und kann außerdem geändert werden.

[BlackJack]

Wobei man mit dem Ändern sehr vorsichtig sein sollte, denn man kann Werte setzen, die dann aber nie erreicht werden (können), weil das Programm vorher hart abstürzt, also gewaltsam vom Betriebssystem beendet wird und sich nicht sauber selber beendet.

@MEL: Man kann a) und b) auch beantworten ohne den konkreten Wert zu kennen, in dem man einfach ein Limit auf n Stapelrahmen annimmt und die Antwort als Formel in Abhängigkeit von diesem festen aber beliebigen n angibt.

[cofi]

Och ihr tut grad so als wollte der OP das selbst beantworten. Da er sich aber nichtmal die Aufgabenstellung umschreibt bzw das wichtige extrahiert ...

[jerch]

weiß jemand die antworte von diese aufgabe

Jab, die Antwort weiss jemand.

[Sirius3]

Jab, die Antwort weiss jemand.

Unter anderem mit großer Wahrscheinlichkeit der Aufgabensteller.
Einfach mal den fragen

[BlackJack]

Hm, bei a) könnte man doch eigentlich auch sagen es kann schon bei einer leeren Liste passieren. Das da *eventuell* ein Stapelüberlauf passiert.

[Sirius3]

@Blackjack: Wie kann ich bei vernünftigem Rekursionslimit bei einer leeren Liste einen Überlauf erzeugen?
Dass bei b) die leere Liste die richtige Lösung ist, ist ja klar.

[BlackJack]

@Sirius3: Da steht nirgends etwas von einem vernünftigen Rekursionslimit, und auch nicht der wievielte verschachtelte Aufruf der zur Sortierfunktion ist.