递归函数 c++ 的复杂性

Question

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

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

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

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(。