时间复杂度如果是对数阶或者是指数阶，代码会是什么样子啊？是指什么样子的操作呢？

Question

如题所述

Answer 1

一、对数阶：

void aFunc(int n) {    
    for (int i = 2; i < n; i++) {
        i *= 2;
        printf("%i\n", i);
    }
}

解释：假设循环次数为 t，则循环条件满足 2^t < n。
可以得出，执行次数t = log(2)(n)，即 T(n) = log(2)(n)，可见时间复杂度为 O(log(2)(n))，即 O(log n)。

二、指数阶：

long aFunc(int n) {    
    if (n <= 1) {        
        return 1;
    } else {        
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

    解释：显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。
显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列，通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。
所以该方法的时间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)。

Answer 2

就是运算的次数，比如问题规模是n，运行时间为klogn就是对数阶的追问

有没有具体的代码可以看一下呢？

追答

for(i = 0; i< n; i++)
{
printf("%d", i);
}
这个就是复杂度为n