Evaluating the average time complexity of a given bubblesort algorithm.
-
16-10-2019 - |
Pergunta
Considering this pseudo-code of a bubblesort:
FOR i := 0 TO arraylength(list) STEP 1
switched := false
FOR j := 0 TO arraylength(list)-(i+1) STEP 1
IF list[j] > list[j + 1] THEN
switch(list,j,j+1)
switched := true
ENDIF
NEXT
IF switched = false THEN
break
ENDIF
NEXT
What would be the basic ideas I would have to keep in mind to evaluate the average time-complexity? I already accomplished calculating the worst and best cases, but I am stuck deliberating how to evaluate the average complexity of the inner loop, to form the equation.
The worst case equation is:
$$ \sum_{i=0}^n \left(\sum_{j=0}^{n -(i+1)}O(1) + O(1)\right) = O(\frac{n^2}{2} + \frac{n}{2}) = O(n^2) $$
in which the inner sigma represents the inner loop, and the outer sigma represents the outer loop. I think that I need to change both sigmas due to the "if-then-break"-clause, which might affect the outer sigma but also due to the if-clause in the inner loop, which will affect the actions done during a loop (4 actions + 1 comparison if true, else just 1 comparison).
For clarification on the term average-time: This sorting algorithm will need different time on different lists (of the same length), as the algorithm might need more or less steps through/within the loops until the list is completely in order. I try to find a mathematical (non statistical way) of evaluating the average of those rounds needed.
For this I expect any order to be of the same possibility.
Solução
For lists of length $n$, average usually means that you have to start with a uniform distribution on all $n!$ permutations of [$1$, .., $n$]: that will be all the lists you have to consider.
Your average complexity would then be the sum of the number of step for all lists divided by $n!$.
For a given list $(x_i)_i$, the number of steps of your algorithm is $nd$ where $d$ is the greatest distance between a element $x_i$ and his rightful location $i$ (but only if it has to move to the left), that is $\max_i(\max(1,i-x_i))$.
Then you do the math: for each $d$ find the number $c_d$ of lists with this particular maximal distance, then the expected value of $d$ is:
$$\frac1{n!}\ \sum_{d=0}^n{\ dc_d}$$
And that's the basic thoughts without the hardest part which is finding $c_d$. Maybe there is a simpler solution though.
EDIT: added `expected'
Outras dicas
Recall that a pair $(A[i], A[j])$ (resp. $(i,j)$) is inverted if $i < j$ and $A[i] > A[j]$.
Assuming your algorithm performs one swap for each inversion, the running time of your algorithm will depend on the number of inversions.
Calculating the expected number of inversions in a uniform random permutation is easy:
Let $P$ be a permutation, and let $R(P)$ be the reverse of $P$. For example, if $P = 2,1,3,4$ then $R(P) = 4,3,1,2$.
For each pair of indices $(i,j)$ there is an inversion in exactly one of either $P$ or $R(P)$.
Since the total number of pairs is $n(n-1)/2$, and the total number and each pair is inverted in exactly half of the permutations, assuming all permutations are equally likely, the expected number of inversions is:
$$\frac{n(n-1)}{4}$$
Number of swaps < Number of iterations (in both optimized as well as simple bubble case scenario)
Number of Inversions = Number of swaps.
Therefore, Number of Iterations > $\frac{n(n-1)}{4}$
Thus, Average case complexity is $\omega(n^2)$. But, since average case cant exceed worst case, we get that it is $O(n^2)$,
This gives us : Average Time = $\theta(n^2)$
(Time complexity = Number of iteration no. of iterations > no. of swaps)
in this document, the average time complexity of bubble sort reached O(nlog(n))! http://algo.inria.fr/flajolet/Publications/ViFl90.pdf