c循环函数计算时间复杂度

Question

我正在学习计算算法的时间复杂度。可以计算简单循环和嵌套循环，但如果循环内有赋值，我该如何计算。例如：

void f(int n){
    int count=0;
    for(int i=2;i<=n;i++){
        if(i%2==0){
            count++;
        }
        else{
            i=(i-1)*i;
        }
    }
}

i = (i-1)*i影响循环次数运行。如何计算此函数的时间复杂度？

Answer 1

由于 i * (i-1) 始终为偶数 ((i * (i-1)) % 2 == 0)，如果循环中 else 部分为真一次，则 i++ 使 i奇数。结果，在循环中的第一个奇数 i 之后，条件总是进入 else 部分。

因此，在第一次迭代之后，i 将等于 3，这是奇数并且在 else 部分内，i 将增加i * (i-1) +‌ 1 在每次迭代中。因此，如果我们用 T(n) 表示循环的时间复杂度，我们可以渐进地写成：T(n) = T(\sqrt(n)) + 1。所以，如果 n = 2^{2^k}, T(n) = k = log(log(n)).

Answer 2

没有通用规则来计算此类算法的时间复杂度。你必须使用你的数学知识来获得复杂性。

对于这个特定的算法，我会这样处理。

由于最初 i=2 并且它是偶数，让我们忽略第一次迭代。所以我只考虑从 i=3。从那时起，我将永远是奇怪的。

您的表达式 i = (i-1)*i 以及 for 循环中的 i++ 最终计算为 i = (i-1)*i+1

如果将i=3视为第1次迭代，i(j)是第j次迭代中i的值，则i(1)=3。还有

i(j) = [i(j-1)]^2 - i(j-1) + 1

上面的方程称为递归关系，有标准的数学方法可以求解它并得到 i 的值作为 j 的函数。有时有可能获得，有时可能非常困难或不可能。坦率地说，我不知道如何解决这个问题。

但一般来说，我们不会遇到需要您走那么远的情况。在实际情况下，我只是假设复杂度是对数的，因为 i 的值呈指数增长。

c循环函数计算时间复杂度

c loop function computing time complexity

c

algorithm

time-complexity