Wie schreibe ich Algorithmus bei einer Laufzeit

Question

Ich nehme gerade einen Algorithmus Analyse Kurs. Eine der Fragen eines Quiz war es, einen Algorithmus mit der Laufzeit T(n) = 4T(3n/4) + n^2 zu schreiben, wo der Algorithmus nichts Wichtiges zu tun hat.

Ich konnte keine ähnlichen Beispiele finden, daher bin ich mir nicht sicher, wie es weitergeht.

Answer 1

Um zu vereinfachen, über diese Art von Problem nachzudenken, verwenden Sie einfach ein Array von n Elemente, um ein Problem der Größe n darzustellen.

Dann stellt die Laufzeit T(n) den Algorithmus dar, der auf dem Array ausgeführt wird.

Die Laufzeit 4T(3n/4) stellt den Algorithmus dar, der drei Viertel des Arrays vier Mal ausgeführt wird.

Die Laufzeit n^2 repräsentiert eine quadratische Operation auf dem Array (z. B. eine Blasensortierung).

silly_algo (arr[], n) 
    if n == 0 return 
    for i : 1..4 
     silly_algo(arr, 3*n/4) 
    bubblesort(arr, n)