时间复杂度：if/else for循环下

Question

如果在类似下面的情况下（for 循环下的 if/else 语句）时间复杂度是 O(n) 还是 O(n^2):

def power_dic (n,k)
    if (k=0):
        return 1
    elif (k mod 2 = 0):
        return power(n*n, k/2)
    else
        return n*power_dic(n, k-1)

以上代码计算 n^k。

Answer 1

在这种情况下，您需要分析代码的整体行为。每个return语句将被调用多少次，然后与输入之间的关系。

在这个具体的例子中：

时间复杂度O(logk)（假设所有int乘法都是O(1)）。

每调用一次return power(n*n, k/2)，最多调用一次return n*power_dic(n, k-1)⁽¹⁾.

此外，return power(n*n, k/2) 被调用了 O(logk) 次，因为每次调用它都会减半。

这意味着，您的总复杂度为 2*logn，即 O(logk)。

(1) 除了最后一点，你调用 power_dic(n,1)，但那一次不会改变答案。

Time complexity: if/else under for loop