algorithm - 比较给定步骤的两种算法的复杂性

Question

假设您有一个大小为 n 的数据集和两个处理该数据的算法以同样的方式设置。算法 A 用了 10 个步骤来处理数据集中的每个项目。算法 B 在 100 个步骤中处理每个项目。会有什么复杂性属于这两种算法吗？

我从问题中得出算法 A 完成每个项目的处理的复杂度是算法 B 的 1/10，并使用问题中接受的答案中提供的图表:What is a plain English explanation of "Big O" notation?我得出的结论是算法 B 的复杂度为 O(n^2)，算法 A 的复杂度为 O(n)，但我很难在没有实现的情况下得出超出该范围的结论。

Answer 1

在开始对时间复杂度做出任何结论之前，您需要多个数据点。算法A和算法B之间10步和100步的差异可能有很多不同的原因:

1. 加法常量差异:无论输入如何，算法 A 总是比算法 B 快 90 步。在这种情况下，两种算法将具有相同的时间复杂度。

2. 标量乘法差异:无论输入如何，算法 A 总是比算法 B 快 10 倍。在这种情况下，两种算法将具有相同的时间复杂度。

3. 您提出的情况，其中 B 是 O(n^2)，A 是 O(n)

4. 还有很多很多其他的可能性。