这个算法的 big-o 表示法是什么？

Question

由循环中 N 的乘法组成的算法的大 O 表示法是什么。void testing(int n) {    for(int i =0; i<n;i++) {        n=n*2;        System.out.println("hi"+n);    }}

Answer 1

我会尽量严谨地回答我的问题。

编辑：忘了说，我们假设比较、赋值和乘法等每个操作的复杂度都是O(1)

简而言之，该算法在大多数情况下不会终止，因此没有为其定义复杂度。复杂度是算法成本C的某种上限，说明O(n)复杂度意味着C <= kxn, k > 0。非终止算法的成本是无限的，并且inf > inf是未定义的。

然后，让我们看看为什么你的算法是非终止的：

每次迭代，如果i < n ，我们继续。然而，每次迭代n都乘以2。在检查循环条件时，我们可以看到i和n的值之间的关系： n = n0x2^i，其中n0是n的初始值。因此，您的算法只会在n0 <= 0时终止，并且当这种情况发生时，它不会进入循环一次。

Answer 2

我尝试在我的 IDE 中运行你的代码，我发现它是一个无限循环。算法复杂性仅针对算法定义，根据（最常接受的）定义必须终止。当一个程序没有终止时，它就不是一个算法。所以它没有“算法时间复杂度”。