基于时间复杂度，这些片段真的很困惑

Question

大家好，我很长一段时间都对两个代码片段的时间复杂度感到困惑

例如，让我们看一个列表，该列表有 n 个项目，但在下一行中，我将其初始化为 ArrayList 的新实例。

   List<Integer> temp = List.of(1,2,3,4,5);
   temp = new ArrayList<>(); // I believe the time complexity is O(1)

所以上面代码片段中的伙计们，它真的是 O(1) 是因为它创建了一个新的实例对象并指向它，还是我在这里错了？

另一个片段是

   int counter = any value;
   for(int i = 0;i<n;i*=counter)// I guess its O(n)

在上面的代码片段中，我猜它的 O(n) coz 计数器是可变的并且可以有任何不固定的随机值或者是 log(n)？

请大家多多指教，谢谢。

Answer 1

So guys in the above snippet is it really O(1) coz it creates a new instance object and points to it or am i wrong here?

第 1 行 List<Integer> temp = List.of(1,2,3,4,5) 是 O(n)。在幕后，Java 实际上遍历元素以在将它们设置到 List 持有的底层数组之前进行空值检查。

第 2 行 temp = new ArrayList<>() 是 O(1)。初始化新列表所花费的时间是恒定的；这里没有变量。

当你将整个代码片段作为一个整体（第 1 + 2 行一起）考虑时，它是 O(n)，因为我们总是在算法中取最高的复杂度。

In the above snippet i guess its O(n) coz counter is variable and can have any random value which is not fixed or is it log(n) ?

鉴于您将循环初始化为 i = 1，并且 n 和 counter 都是变量而不是常量，时间复杂度将为 O (log _counter n).

在循环中，每次迭代后，剩余的迭代次数将减少（除以）counter 倍。因此时间复杂度是对数的。你可以把“log _c n”想成是说“从n开始，为了达到1你需要递归除以c的次数".

但是，如果您真的打算将循环初始化为 i = 0，它只会无限执行。

Really confused for these snippets based on Time Complexity