两种算法复杂度的比较

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. 很多很多其他的可能性。