具有恒定循环和递归的给定函数的时间复杂度

Question

这个的时间复杂度是多少，会是 O(????logn)？

fun(int n) {
    if (n < 2)
        return 1;
    int counter = 0;
    for (int i = 1; i <= 8; i++)
        fun(n / 2);
    for (int i = 1; i <= Math.pow(n, 3); i++)
        counter++;
}

Answer 1

函数的复杂度为：

T(n) = n^3 + 8*T(n/2)

• n^3来自最后一个循环，从1到n^3
• 8*T(n/2)从调用fun(n/2)8 次（在第一个循环中）

要找到复杂性，可以使用主定理：a = 8, b = 2, f(n) = n^3

使用案例2：

log_2(8) = 3，而且确实f(n)是在Theta(n^3)，使这个函数复杂度为O(n^3*logn)。