C语言 确定这段代码的时间复杂度?

Question

我认为这段代码的时间复杂度是0 (n^2)但我不确定如果有人能解释一下这段代码的时间复杂度会很有帮助

int func2()
{
int i, j, k = 0;
scanf("%d", &n);
for (i = 1; i < n; i++)
{
i -= 1;
i *= 2;
k = k + i;
for (j = 1; j < n; j++);
}
}

Answer 1

在我看来这是一个无限循环，所以时间复杂度是O(∞)。

外循环第一次迭代时，i -= 1将i置为0。乘以2还是0

循环迭代i++将i增加到1，下一次迭代将重复上述计算。

Answer 2

我是时间复杂度的初学者，但这些是我的观点:-外部for循环处于无限循环的状态，因为在外部循环的第一次迭代时，执行从i=1开始。在执行i -= 1时，它将设置i=0。执行i*=2时，i的值保持0。在递增阶段，i递增，i=1。所以同样的过程发生了。因此，i的值保持不变，导致它无限期地运行。现在，进入外部for循环的是一个嵌套的for(在变量j中)循环，后面跟着一个分号。这导致它的时间复杂度为0(1)。因此，最终的总体时间复杂度可以预期为O(无穷大)。

Answer 3

首先，这里没有声明'n'，输入值被赋给了它。

第二，从技术上讲，这段代码是一个无限循环(以一种荒谬的困难的方式完成)，对于非终止的，永远运行的算法，时间复杂度是"未定义的"，因为根据算法分析的原则，时间复杂度只计算那些执行任务的算法。

如果这将是一个终止循环，则该函数的时间复杂度O(n^2)本质上是二次的，因为for(;;)嵌套在另一个for(;;)中，其中包含O(1) -线性时间复杂度。高阶复杂度(O(n^2))取代。