我做了什么：我测量了处理 100、1000、10000、100000、1000000 个项目所花费的时间。此处测量：https : //github.com/DimaBond174/cache_single_thread 。
然后我假设 O(n) 与 n 成比例增加，并计算关于 O(n) 的其余算法..
有处理 100、1000、10000、100000、1000000 个项目的时间测量，我们现在如何将算法归因于 O(1)、O(log n)、O(n)、O(n log n) 或 O(n) ^2) ?
让我们将 N 定义为可能的数据输入之一。一个算法可以有不同的 Big O 值，具体取决于您指的是哪个输入，但通常只有一个您关心的大输入。没有问题的算法，你只能猜测。但是，有一些指南可以帮助您确定它是哪个。
一般规则：
O(1) - 无论数据大小如何，程序的速度几乎没有变化。为此，程序根本不能对相关数据进行循环操作。
O(log N) - 当 N 以对数曲线急剧增加时，程序会稍微减慢速度。为此，循环必须仅通过一小部分数据。（例如，二进制搜索）。
O(N) - 程序的速度与输入数据的大小成正比。如果对数据的每个单元执行操作，就会得到这个。您不能有任何类型的嵌套循环（作用于数据）。
O(N log N) - 程序的速度因较大的输入而显着降低。当您在循环中嵌套 O(logN) 操作时会发生这种情况，否则该操作将是 O(N)。例如，您有一个循环对每个数据单元进行二分搜索。
O(N^2) - 程序会因输入较大而缓慢爬行，并最终因足够大的数据而停滞。当您有嵌套循环时会发生这种情况。同上，但这次嵌套循环是 O(N) 而不是 O(log N)
因此，尝试将循环操作视为 O(N) 或 O(log N)。然后，每当您有嵌套时，将它们相乘。如果循环不是嵌套的，它们不会像这样相乘。因此，彼此分开的两个循环将简单地为 O(2N) 而不是 O(N^2)。
还要记住，你可能在引擎盖下有循环，所以你也应该考虑它们。例如，如果您在 Java 中执行了 Arrays.sort(X) 之类的操作，那将是一个 O(N logN) 操作。因此，如果出于某种原因将其放入循环中，那么您的程序将比您想象的要慢得多。
希望这能回答你的问题。