Analysieren Laufzeit, Big O

Question

Ich habe Probleme mit der Analyse der Zeit Komplexität eines Algorithmus.

Zum Beispiel der folgende Haskell-Code, der eine Liste sortiert.

sort xs 
|isSorted xs= xs 
|otherwise= sort (check xs) 
    where 
    isSorted xs=all (==True) (zipWith (<=) xs (drop 1 xs)) 
    check [] =[] 
    check [x]=[x] 
    check (x:y:xs) 
     |x<=y = x:check (y:xs) 
     |otherwise=y:check (x:xs) 

So für n die Länge der Liste und t_isSorted (n), um die Laufzeitfunktion ist: es gibt eine konstante T_DROP (n) = c und t_all (n) = n, t_zipWith (n) = n :

t_isSorted(n)= c + n +n 

Für T_CHECK:

t_check(1)=c1 

    t_check(n)=c2 + t_check(n-1), c2= for comparing and changing an element 
      . 
      . 
      . 
    t_check(n)=i*c2 + tcheck_(n-i), with i=n-1 
      =(n-1)*c2 + t_check(1) 
      =n*c2 - c2 + c1 

Und wie genau muss ich denen erhalten t_sort (n) kombinieren? Ich denke, im schlimmsten Fall muss sort xs n-1 mal laufen.

Answer 1

isSorted ist in der Tat O(n), da es von zipWith dominiert wird, die wiederum O(n) ist, da es einen linearen Durchlauf über sein Argument macht.

check selbst ist O(n), da es nur einmal pro Ausführung selbst aufruft, und es entfernt immer eine konstante Anzahl von Elementen aus der Liste. Der schnellste Sortieralgorithmus (ohne etwas mehr über die Liste zu wissen) läuft in O(n*log(n)) (entspricht O(log(n!)) Zeit). Es gibt einen mathematischen Beweis dafür, und dieser Algorithmus ist schneller, so dass es unmöglich ist, die ganze Liste zu sortieren.

check bewegt nur die Dinge einen Schritt; es ist effektiv ein einziger Durchgang von Blasensortieren.

Betrachten Sie diese Liste Sortierung: [3,2,1]

check [3,2,1] = 2:(check [3,1]) -- since 3 > 2 
check [3,1] = 1:(check [3]) -- since 3 > 1 
check [3] = [3] 

die [2,1,3] die "sortiert" Liste zurückkehren würde.

Dann, solange die Liste nicht sortiert ist, wir Schleife. Da wir möglicherweise nur ein Element an die richtige Position setzen (wie im obigen Beispiel 3), benötigen wir möglicherweise O(n) Schleifeniterationen.

Diese beträgt bei einer Zeitkomplexität von O(n) * O(n) = O(n^2)

Answer 2

Die Zeitkomplexität O(n^2) ist.

Sie haben recht, ein Schritt dauert O(n) Zeit (für beide isSorted und check Funktionen). Es heißt nicht mehr als n mal (vielleicht sogar n - 1, es spielt keine Rolle für die zeitliche Komplexität) (nach dem ersten Aufruf ist das größte Element garantiert das letzte, dasselbe gilt für das zweitgrößte nach dem zweiter Aufruf, wir können beweisen, dass die letzten k Elemente die größten sind und nach k Rufe richtig sortiert sind). Es tauscht nur benachbarte Elemente aus, so dass pro Schritt maximal eine Inversion entfernt wird. Da die Anzahl der Inversionen im schlimmsten Fall O(n^2) ist (nämlich n * (n - 1)/2), ist die Zeitkomplexität O(n^2).