计算大 O 符号 O(n) 和 O(n^2)

Question

我有一个程序可以从 ArrayList 中获取数据，这需要 O(n) 的时间。

但也有一个嵌套的 for 循环，它需要 O(n^2) 时间。

程序的时间复杂度是 O(n^2) 还是 O(n^3)？

Answer 1

这取决于这两个部分如何相互作用。如果它们互相调用（例如，对于列表中的每个元素 (O(n))，您执行一个对整个列表执行嵌套循环的方法 (O(n²)) ，你将它们相乘得到 O(n³) 时间复杂度。

如果以串行方式调用它们 - 即，您遍历列表 (O(n))，一旦您执行 O(n²)算法，反之亦然，O(n)部分相对于O(n²)部分可以忽略不计，整体时间复杂度为O(n² ).