大 O - 递归代替乘法

Question

正在研究一种替代乘法的方法。

public static int mult(int num, int repeat){
        if (repeat == 0) return 0;
        if (repeat == 1) return num;
        return num + mult(num, repeat - 1); 
    }

就时间和 space 复杂度而言，这是否为 O(k) 时间，其中 k 是 重复 和 O(1) space ？

Answer 1

这是 O(K) 时间，因为您将在每个 repeat 中调用一次此函数，并且每次调用都是 O(1)。然而，它也是 O(k) space a 在你达到终止条件之前你会有 k 个堆栈帧（在没有 tail-call 递归优化的情况下）。