0

这是插入排序的两个版本，我用伪代码实现一个，一个直接实现。我想知道哪个版本需要更多的步骤和空间（即使是一点空间也很复杂）。

void insertion_sort(int a[], int n) {
    int key, i, j;
    for(i = 1; i < n; i++) {
        key = a[i];
        j = i - 1;
        while(j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }       
}

和这个

insertion_sort(item s[], int n) {
  int i,j;
  for (i=1; i<n; i++) {
    j=i;
    while ((j>0) && (s[j] < s[j-1])) {
      swap(&s[j],&s[j-1]);
      j = j-1;
    }
  }
}

这是示例排序数组 a = {5, 2, 4, 6, 1, 3}。在我看来，第二个版本采取了更多步骤，因为它一个接一个地交换数字，而第一个版本在 while 循环中交换更大的数字，然后交换最小的数字。例如：直到 index = 3，两个版本都采取相同的步骤，但是当 index = 4 时，即交换编号 1，第 2 次比第 1 次采取更多的步骤。你怎么看？

4

4 回答 4

2

“步数”不是衡量任何事情的有用指标。

一步是一条线吗？一份声明？一种表达？汇编指令？CPU微操作？

也就是说，您的“步骤”被转换为汇编程序，然后进行优化，生成的指令可能具有不同的（并且可能是可变的）运行时成本。

您可能会问的明智问题：

1 什么是算法复杂度？

正如 Rafe Kettler 的评论和 Arpit 的回答中所给出的，这是关于算法如何随着输入大小的增长而扩展

2表现如何

如果您想知道哪个更快（对于某些输入集），您应该测量它。

如果您只想知道哪个执行更多交换，为什么不编写一个swap每次调用全局计数器时递增的函数并找出答案？

于 2013-03-26T18:46:10.813 回答
1

Number of swaps is the wrong term, you should count the number of assignments. swap() expands to three assignments and you therefore usually end up with more assignments in the second version without saving space (you may not have key in the second version, but swap() internally has something similar).

于 2013-03-26T18:48:52.387 回答
0

两个版本都使用两个循环。所以复杂O(n*n)的时间。考虑所有其他语句的常量（1）时间。

于 2013-03-26T18:26:21.900 回答
0

让我们逐行分析。我假设交换的复杂度为 3

a) 计算复杂度：（ 3+(n-1)*(1+1+((n-1)/2)*(1+1+1)*(1+1)+1)=1+(n-1)*(3n)=3n^2-3n+1 我们使用 n/2，因为它似乎是连续最坏情况的平均值）。

内存：3 个整数，+1（for 循环）

b) 计算复杂度：2+(n-1) (1+((n-1))/2(1+1+1) (3+1))=2+(n-1)*(6n-5 )=6n^2-11n+7

内存：2 个整数，+交换成本（很可能是额外的 1 个整数）

不计算输入内存，因为在两种情况下都是相同的。希望能帮助到你。

于 2013-03-26T18:46:27.283 回答