我正在学习复杂性理论类(class)，因此它需要一些数学背景知识，但我遇到了问题。 所以当我尝试做一些练习时，我陷入了下面的例子
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)
以及我对分析到 n(n+1)/2 – 1 的第 4 行不理解或困惑的地方， 和第 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)
最佳答案
第 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-1 和 1。总和由 (n-1)(n-1+1)/2 给出。因子 3 来自 3 行 (5,6,7)，每行都被执行 (n-1)(n)/2 次
关于algorithm - 复杂性理论-排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12763524/