1

我有以下算法:

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。拜托,有人愿意向我解释我哪里弄错了吗?

4

1 回答 1

0

这是一种以数学方式表示您的算法的正式方式(Sigma 表示法):

在此处输入图像描述

c替换为外循环中的操作数,将c'替换为内循环中的操作数。

于 2014-03-13T22:09:21.857 回答