Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


6. Analyse von Algorithmen



Übungen

  1. Angenommen, es ist bekannt, daß die Laufzeit eines Algorithmus O(N log N) ist und daß die Laufzeit eines anderen Algorithmus O(N3) ist. Was sagt das über die relative Leistungsfähigkeit der Algorithmen aus?
  2. Angenommen, es ist bekannt, daß die Laufzeit eines Algorithmus stets ungefähr N log N ist, und daß die Laufzeit eines anderen Algorithmus O(N3) ist. Was sagt das über die relative Leistungsfähigkeit der Algorithmen aus?
  3. Angenommen, es ist bekannt, daß die Laufzeit eines Algorithmus stets ungefähr N log N ist, und daß die Laufzeit eines anderen Algorithmus immer ungefähr N3 ist. Was sagt das über die relative Leistungsfähigkeit der Algorithmen aus?
  4. Erklären Sie den Unterschied zwischen O(1) und O(2).
  5. Lösen Sie die rekurrente Beziehung
    CN = CN/2 + N2, für N >= 2, mit C1 = 0,
    wenn N eine Zweierpotenz ist.
  6. Für welche Werte von N gilt 10N lg N > 2N2?
  7. Schreiben Sie ein Programm zur Berechnung des exakten Wertes von CN in Formel 2, wie im Kapitel 5 erläutert wurde. Vergleichen Sie die Ergebnisse mit lgN.
  8. Beweisen Sie, daß die exakte Lösung von Formel 2 lg N + O(1) lautet.
  9. Schreiben Sie ein rekursives Programm zur Berechnung der größten ganzen Zahl, die kleiner ist als log2 N. (Hinweis: Für N > 1 ist der Wert dieser Funktion für N div 2 um eins kleiner als für N.)
  10. Schreiben Sie ein iteratives Programm für das Problem der vorangehenden Übung. Schreiben Sie danach ein Programm, das die Berechnung unter Verwendung von Bibliotheksroutinen von Pascal vornimmt. Falls es mit Ihrem Computersystem möglich ist, vergleichen Sie die Leistungsfähigkeit dieser drei Programme.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]