c - 算法复杂度计算

Question

我开始学习如何用 c 语言编写代码。 目前，我正在尝试实现一个程序来显示类似于这样的输出:

{ 欢迎使用 CSE 分拣系统

---

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

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

排序后的数组:

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

Answer 1

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

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