algorithm - 排序代码的运行时间

Question

Sort(B)
for i = 0 to (n-1)
    x = (i+1);
    for j = (i+2) to n 
        if B[x] > B[j]
           x = j;
    if x != (i+1)
       temp = B[i+1];
       B[i+1] = B[x];
       B[x] = temp;

运行时间 T(n) 是多少？问题出在内部循环(对于 j = (i+2) 到 n )内循环的最坏情况是什么？最好的情况是什么？我认为它们是相同的，因为它是独立的，但我想确定一下。

Answer 1

运行时间为O(n^2)。

每个内部循环花费 O(n-i) 时间，将 i 的值从 0 增加到 n-1。

这给你时间复杂度:

T(n) <= CONST*(n-0 + n-1 + n-2 + ... + n-(n-1))   = 
     = CONST*(1 + 2 + ... + n) = CONST*(n(n+1)/2)

最后一个等式来自sum of arithmetic progression .

因为 n(n+1)/2 是 O(n^2)，所以这就是时间复杂度。