算法复杂度计算

Question

我开始学习如何用c语言编写代码。目前，我正在尝试实现一个程序，该程序将显示类似于以下内容的输出：

{欢迎使用CSE分拣系统

请输入您的大小数组：

请选择下列排序算法之一：

1-气泡分类

2-插入排序

3-选择排序

4-快速排序

你的选择：

您的数组已在x步骤中使用选择排序进行排序。

排序后的数组：}

我的程序基本上已经完成，但我在确定如何计算排序过程中使用的x步数时遇到了困难。如何推断算法使用的“步骤”的数目？

Answer 1

这听起来是一个有趣的，但有点挑战性的问题来解决。“步骤”本身是相当抽象的。

假设我有一些任意的排序函数：

void lameSort(int* array, int length) {
  int i;
  for (i = 0; i < length; ++i) {
    if (array[i] == 5) {
      int tmp = array[i];
      array[i] = array[i - 1];
      array[i - 1] = tmp;
    }
  }
}

你到底会把“步骤”定义为什么？你可以说

• 初始化索引=1步
• 用5=n步(数组长度)比较每个数组元素
• 初始化临时变量=1步
• ..。等

你将不得不以某种方式对这些“步骤”进行计数。

而且，人们通常不会用精确的步骤来衡量算法的复杂性。它们用大-O表示法来表示运行时间/存储复杂度，最高阶多项式是运行时间。

Answer 2

对于复杂性注释，go 这里

对于复杂性计算示例，请参见这里

这两门课都是用一种简单易懂的语言来解释的。