algorithm - 如何计算算法的运行时间

Question

我有以下算法:

for(i = 1; i < n; i++){ 
   SmallPos = i;
   Smallest = Array[SmallPos]; 
   for(j = i + 1; j <= n; j++)
            if (Array[j] < Smallest) { 
                   SmallPos = j;
                   Smallest = Array[SmallPos];
                } 
   Array[SmallPos] = Array[i]; 
   Array[i] = Smallest;
}

这是我的计算:

For the nested loop, I find a time complexity of
1 ("int i = 0") + n+1 ("i < n") + n ("i++")
* [1 ("j = i + 1") + n+1 ("j < n") + n ("j++")]
+ 3n (for the if-statement and the statements in it)
+ 4n (the 2 statements before the inner for-loop and the final 2 statements after the  inner for-loop). 
This is (1 + n + 1 + n)(1 + 1 + n + n) + 7n = (2 + 2n)(2 + 2n) + 7n = 4n^2 + 15n + 4.

但不幸的是，教科书得到了T(n) = 2n^2 +4n -5。拜托，有人愿意向我解释我哪里错了吗？

Answer 1

这里是用数学方式(Sigma 表示法)表示您的算法的正式方式:

用外循环中的操作数替换c，用内循环中的操作数替换c'。