bubble sort komplexity analysis

Question

Vielleicht wurde diese Frage ein paar Mal gestellt, aber ich habe Zweifel. In dem folgenden Algorithmus:

BubbleSort(v[n]) 
i←0 
exchange←V 
while (exchange) 
    exchange←F 
    i←i+1 
    for pos=0 to n-i 
     if v[pos]>v[pos+1] then 
      swap(v[pos],v[pos+1]) 
      exchange←V 
     endif 
    endfor 
endwhile 

Ich habe es wie folgt analysiert:

aber ich habe Zweifel, ob ich das Richtige getan zu haben, denn wenn ich die innere Schleife analysieren kann ich sagen, dass ich habe:

wo ich, dass c hängt von dem Wert der äußeren while-Schleife sagen kann, weil es aktiv sein könnte oder nicht, welche Analyse ist genauer von den beiden, die ich hier umrissen habe?

Danke

Answer 1

Ihre beiden Analysen sind falsch.

Wenn Sie in der ersten Analyse die äußere Summe eliminieren, behandeln Sie den Ausdruck innerhalb der Summe so, als ob er unabhängig von der Summationsvariablen ist, wenn dies nicht der Fall ist. Ihre Arbeit danach hat eine i darin, selbst nachdem die Summe, die i definiert, beseitigt ist, ein klares Zeichen, dass Sie etwas falsch gemacht haben.

In Ihrer zweiten Analyse vergessen Sie c nach der ....