0

为明天的期中考试而学习，而这些时间复杂性让我很挣扎。我将回顾书中的简单示例，并针对此示例

交换排序

void exchangesort (int n, keytype S[])
{
  index i, j;
  for(i=1; i<=n-1; i++)
    for(j=i+1; j<=n; j++)
      if(S[j] < S[i])
        exchange S[i] and S[j];
}

对于这种 Exchange 排序的“每个案例时间复杂度”，我理解我们几乎分析jfor 循环的部分，因为它具有基本操作（交换）。因此，如果您列出通行证总数，则由下式给出：

T(n) = (n-1) + (n-2) + (n-3) + ... + 1 = (n-1)n/2

现在我的问题是...... 1 来自哪里？我以为是n-1 + n-2 +... + n。

此外，我真正不明白的是如何提出(n-1)n/2.
这显然是我在中期必须想出的，通过观察，(n-1)n/2并不直观......我知道如何想出T(n) = (n-1) + (n-2)等等，我想......

有人可以用外行的话向我解释一下，这样我明天的期中考试就可以想出这样的答案吗？

4

4 回答 4

4

在内部循环中，j从i+1到n，即通过n-i值。所以总的来说，有

sum_{i = 1 to n-1} (n-i)

步骤，(n-1) + (n-2) + ... + (n - (n-1)) = (n-1) + (n-2) + ... . 1.

现在，对于第一个k正整数的和，有一个封闭的公式，它是

k*(k+1)/2

在这里，k = n-1。

要计算出第一个k正整数之和的公式，有几种不错的方法，如robert king 的回答中所述。据称，高斯五岁时用第一种方法计算出来，老师让学生计算从 1 到 100 的整数之和，希望能有几分钟安静的时间。最好看看是否这样安排：

  1   +   2   + ... + (n-1) +   n
  n   + (n-1) + ... +   2   +   1
----------------------------------
(n+1) + (n+1) + ... + (n+1) + (n+1) = n*(n+1)
于 2012-02-08T19:58:49.460 回答
1

一种解决方法是：

总和=1+2+3+4+...+n

2*总和 = 1+2+3+4+...+n + 1 + 2 + 3 + 4 +...+n = 1+(n) + 2+(n-1) + 3+(n -2)..+ (n)+1

2*总和=1+n + 1+n + 1+n...

2*总和 = n(1+n)

总和=n*(n+1)/2

但更简单的方法是想象一个正方形或网格矩阵。

当 i 下降到每个新行时， j 越过矩阵的对角线和额外的列（因为 i<=j .. 我们知道 j 不能越过对角线）。这意味着所有操作都是矩阵对角线一侧的 (i,j) 的组合。因此，操作的数量是整个矩阵面积的一半。如果矩阵是一个*n 矩阵，那么我们有大约 n*n/2 区域（但由于我们不能将对角线数两次，它实际上是 n*(n-1)/2

于 2012-02-08T20:02:03.440 回答
0

好的，这样想：

When i = 1, inner loop runs (n - 1) times [j = 2 to n]
When i = 2, inner loop runs (n - 2) times [j = 3 to n]
When i = 3, inner loop runs (n - 3) times [j = 4 to n]
....
When i = k, inner loop runs (n - k) times [j = k + 1 to n]
...
When i = n - 1, inner loop runs (n - (n - 1)) = 1 time [j = n to n]

现在总结一下：

(n - 1) + (n - 2) + (n - 3) + ... + 1 = n(n - 1) / 2

在最坏的情况下，exchange将完成n(n - 1) / 2时间。

于 2012-02-08T19:57:50.630 回答
0

该系列从 (n-1) 到 (1) [(n-1), (n-2) ... (n-(n-1))] 在这里检查系列的总和以了解它是如何衍生的。它很容易理解。

于 2012-02-08T19:59:45.080 回答