c++ - 递归函数c ++的复杂性

Question

*我正在尝试计算以下函数的复杂度 Big-Theta-Notation：变量 i 是常量 == 3 *

void g(int i, int n) {
    if (i>0) {
        for (int j=n+10; j>0; j-=5) {
            g(i-2, n);
        }
    }
}

因为是递归函数，我想应该用Master Theorem来计算，但实际上没有n的除法。我会非常感激任何帮助！

标签： c++algorithmtime-complexityruntimecomplexity-theory

Answer 1

递归关系为 T(i, n) = (n+10)T(i-2, n)/5。

奇数和偶数的项i都是具有乘法因子 (n+10)/5 的几何级数。这解决了 T(i, n) = O((n/5)^(i/2)) 或 O(sqrt(n/5)^i) 如果您愿意。