0

我正在学习复杂性理论的课程，所以它需要一些我有问题的数学背景。所以当我试图做一些练习时，我陷入了下面的例子

1)  for (i = 1; i < n; i++) {
2)      SmallPos = i;
3)      Smallest = Array[SmallPos];
4)      for (j = i+1; j <= n; j++)   
5)          if (Array[j] < Smallest) {
6)              SmallPos = j;
7)              Smallest = Array[SmallPos]  
            }   
8)       Array[SmallPos] = Array[i];
9)       Array[i] = Smallest;
    }

因此，总计算时间为：

T(n)    = (n) + 4(n-1) + n(n+1)/2 – 1 + 3[n(n-1) / 2]
        = n  + 4n - 4 + (n^2 + n)/2 – 1 + (3n^2 - 3n) / 2
        = 5n - 5 + (4n2 - 2n) / 2
        = 5n - 5 + 2n^2 - n
        = 2n^2 + 4n - 5 
        = O(n^2)

以及我对第 4 行分析到n(n+1)/2 – 1和第 5 3[n(n-1) / 2]行的不理解或困惑 。我知道正序列的总和是 =n(first+last)/2，但是当我尝试按照我的理解计算它时，它给了我不同的结果。我计算第 4 行，所以它应该是=n((n-1)+2)/2根据n(first+last)/2，但这里是n(n+1)/2 – 1。和3[n(n-1) / 2]一样......我也不明白

这也是分析中写的内容，如果有人可以向我解释，它会有所帮助，

语句 1 执行 n 次 (n - 1 + 1)；语句 2、3、8 和 9（每个表示 O(1) 时间）分别执行 n - 1 次，每次通过外循环时执行一次。在 i = 1 的第一次循环中，语句 4 被执行 n 次；语句 5 执行 n - 1 次，假设最坏的情况是数组的元素按降序排列，语句 6 和 7（每个 O(1) 时间）执行 n - 1 次。

在 i = 2 的第二次通过外部循环时，语句 4 被执行 n - 1 次，语句 5、6 和 7 被执行 n - 2 次，依此类推。因此，语句 4 被执行 (n) + (n -1) +... + 2 次，语句 5、6 和 7 被执行 (n-1) + (n-2) + ... + 2 + 1 次。第一个和等于 n(n+1)/2 - 1，第二个和等于 n(n-1)/2。

因此，总计算时间为：

T(n)    = (n) + 4(n-1) + n(n+1)/2 – 1 + 3[n(n-1) / 2]
        = n  + 4n - 4 + (n^2 + n)/2 – 1 + (3n^2 - 3n) / 2
        = 5n - 5 + (4n2 - 2n) / 2
        = 5n - 5 + 2n^2 - n
        = 2n^2 + 4n - 5 
        = O(n^2)

这是包含此示例的文件的链接： http ://www.google.com.eg/url?sa=t&rct=j&q=Consider+the+sorting+algorithm+shown+below.++Find+the+number+ of+指令+执行+&source=web&cd=1&cad=rja&ved=0CB8QFjAA&url=http%3A%2F%2Fgcu.googlecode.com%2Ffiles%2FAnalysis%2520of%2520Algorithms%2520I.doc&ei=3H5wUNiOINDLswaO3ICYBQ&usg=AFQjCNEBqgrtQldfp6eqdfSYEFKOeKOg

4

1 回答 1

1

第 4 行：正如分析所说，它是执行n+(n-1)+...+2次数。这是(n-1)项的总和。在您使用的公式中，n(first+last)/2,n表示项数。如果您将公式应用于您的n-1术语序列，那么它应该是(n-1)((n)+(2))/2=(n²+n-2)/2=n(n+1)/2-1.

第 5 行：可以使用相同的公式。正如分析所说，您必须计算(n-1)+...+1. 这是n-1项的总和，第一个和最后一个是n-1and 1。总和由 给出(n-1)(n-1+1)/2。因子 3 来自 3 行 (5,6,7)，每行都完成(n-1)(n)/2了

于 2012-10-06T22:08:50.283 回答