计算时间复杂性.需要帮助得出最终结果

Question

为明天的期中考试而学习，这些时间复杂性是我很难解决的问题。我正在复习书中的简单例子，对于这个例子，

交换排序

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排序的"每种情况下的时间复杂性"，我理解我们几乎分析j For循环的部分，因为它有基本的操作（交换）。因此，如果你列出传球总数，它由给出

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)等等，我想。。。

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

Answer 1

在内部循环中，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正整数的和的公式，有几种很好的方法，正如罗伯特·金的回答中所提到的。据说，高斯在五岁时就用第一种方法算出了这个数，老师给学生们一项任务，计算从1到100的整数之和，希望能安静地呆上几分钟。最好看看是否这样安排：

  1   +   2   + ... + (n-1) +   n
  n   + (n-1) + ... +   2   +   1
----------------------------------
(n+1) + (n+1) + ... + (n+1) + (n+1) = n*(n+1)

Answer 2

一种解决方法是：

sum=1+2+3+4++n

2*sum=1+2+3+4++n+1+2+3+4++n=1+（n）+2+（n-1）+3+（n-2）..+（n） +1

2*sum=1+n+1+n+1+n。。。

2*sum=n（1+n）

sum=n*（n+1）/2

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

当我向下到每一个新行时，j穿过矩阵对角线的另一列（当i<=j时……我们知道j不能越过对角线）。这意味着所有运算都是矩阵对角线一侧的（i，j）的组合。因此，运算次数是整个矩阵面积的一半。如果矩阵是一个n*n矩阵，那么我们有大约n*n/2的面积（但由于我们不能将对角线计数为其实际n*（n-1）/2的两倍）

好吧，这样想：

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次。

级数从（n-1）到（1）[（n-1在这里检查级数的和，了解它是如何推导出来的。这很容易理解。