c++ - 您是否将比较之前的步骤包括在排序算法的迭代次数中？

Question

正如问题所述，我脑子里有点空白；当您计算算法完成的步骤数时，是否必须包括尚未进行比较的步骤？

例如:

如果你有一个列表:5,3,7

然后您对其执行冒泡排序。会的；

1)比较5和 3并将它们交换为 5>3 .现在的列表是3,5,7

2) 比较5和 7没有变化 5<7 .现在的列表是3,5,7

3) 比较3和 5没有预期的变化。列表还是3,5,7

4)比较5和 7没有预期的变化。列表还是3,5,7

现在迭代次数是 4 次还是 5 次？ ...还是我完全错了？

谢谢

Answer 1

恕我直言，在尚未执行任何步骤的时间点，步数 = 0。执行一个步骤后，步数 = 1。我真的无法理解你是如何走到执行 4 个步骤的地步的被认为是五个..

无论如何，请记住，它通常被分析为 O(f(n))，其中与 N 无关的术语，如 +-constant，即 +-1 或 +-100 被简单地删除。