java - 计算大 O 表示法 O(n) 和 O(n^2)

Question

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

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

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

标签： javaarraylisttime-complexitybig-o

Answer 1

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

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