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

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 次（在第一个循环中）

要找到复杂度，可以使用 master theorem 和：a = 8, b = 2, f(n) = n^3

使用案例 2：

log_2(8) = 3，实际上 f(n) 在 Theta(n^3) 中，给这个函数复杂度 O(n^3*logn)。

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

Time complexity of the given function with constant loop and recursion

java

algorithm

big-o

time-complexity