测量数字供电的复杂性

Question

我使用分治技术实现了一个为数字 (a^n) 供电的程序。我实现了同一问题的两个版本：

版本 1：

def input_params():
    a=input('Input \'a\' & \'n\' for a^n:')
    n=input('')
    result=power(a,n)
    print (result)

def power(a,n):
    if n<=1:
        return a

    elif n%2==0:
        return pow(power(a,n/2),2)

    else:
        return pow(power(a,(n-1)/2),2)*a

  if __name__ == "__main__":
    input_params()

版本 2：

def input_params():
    a=input('Input \'a\' & \'n\' for a^n:')
    n=input('')
    result=power(a,n)
    print (result)

def power(a,n):
    if n<=1:
        return a

    elif n%2==0:
        return power(a,n/2)*power(a,n/2)

    else:
        return power(a,(n-1)/2)*power(a,(n-1)/2)*a



if __name__ == "__main__":
    input_params()

版本 3：

def input_params():
    a=input('Input \'a\' & \'n\' for a^n:')
    n=input('')
    result=power(a,n)
    print (result)

def power(a,n):
    if n<=1:
        return a

    elif n%2==0:
        return square(power(a,n/2))

    else:
        return square(power(a,(n-1)/2))*a

def square(num):
    return num*num

if __name__ == "__main__":
    input_params()

Q1：以上版本中哪一个具有复杂性θ(lg n)？

Q2：如果版本 2 的复杂度为 θ(lg n)，为什么？因为虽然版本 2 中的问题大小除以二，但子问题的数量也是两个，所以我感觉版本 2 会按照 θ(nlg n) 的顺序增长。

我不确定我的结论。

谢谢

Answer 1

在版本 1 中，没有答案，因为您使用了一个从未定义过的名为 pow 的函数，因此无法真正说出复杂性是什么。

在版本 2 中，存在冗余计算，因此答案取决于您是否认为这些冗余计算是复杂性的一部分（因为它们很容易被忽略）。

尝试根据名为 square 的函数编写版本 3，并包含 square 的定义

在所有情况下，您都需要对基本操作的成本进行一些假设 (*、/ 和 +）您使用。您可能想假设它们的成本都是 O(1)，但您应该在分析中明确这一点。