c - 算法复杂度计算

Question

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

{ 欢迎使用 CSE 分拣系统

---

请输入您的数组大小：
请选择以下排序算法之一：
1 - 冒泡排序
2 - 插入排序
3 - 选择排序
4 - 快速排序
您的选择：

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

排序后的数组：}

我的程序基本完成，但我无法确定如何计算排序过程中使用的 x 步数。如何推断算法使用的“步数”？

Answer 1

对于复杂性符号，请转到此处

对于复杂性计算示例，请转到此处

这两节课都用非常简单易懂的语言进行了解释

Answer 2

程序的复杂度不能简单地计算每个程序执行的指令总数来比较。您需要渐近分析、摊销分析等来分析算法的复杂性。在渐近分析中分析算法的限制行为。

限制行为仅对n ≥ n ₀有效。快速排序的渐近大 O 复杂度为O(n log n)，它小于具有O(n ² )的冒泡排序的复杂度。但是对于 n < n ₀的任意值，即使在平均情况下，冒泡排序也可能会执行快速排序。因此，您计算为比较程序而执行的指令总数的方法可能不会产生正确的结果。

Answer 3

这听起来很有趣，但需要解决一些具有挑战性的问题。“步骤”本身就非常抽象。

假设我有一些任意排序功能：

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 步

• ... ETC

您必须以某种方式计算这些“步骤”中的每一个。

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