Python递归

时间:2022-05-28 chen_冲冲人气:0

递归也是常见算法之一，其时间复杂度一般认为O(logn)，但递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数

举例面试题：求x的n次方

思路一：for循环

def x_n(x,n):
    """
    时间复杂度O(n)
    """
    if n==0:
        return 1
    
    return x*x_n(x,n-1)
    
if __name__=='__main__':
    print(x_n(2,0))
    print(x_n(2,3))
    print(x_n(2,4))

思路二：递归

但是递归时间复杂度未必更优，

比如：

def x_n(x,n):
    """
    时间复杂度O(n)
    """
    if n==0:
        return 1
    
    return x*x_n(x,n-1)
    
if __name__=='__main__':
    print(x_n(2,0))
    print(x_n(2,3))
    print(x_n(2,4))

也可以是：

def x_n(x,n):
    """
    时间复杂度O(n)
    """
    if n==0:
        return 1
    if n%2==1:
        return x*x_n(x,n//2)*x_n(x,n//2)
    
    else:
        return x_n(x,n//2)*x_n(x,n//2)
if __name__=='__main__':
    print(x_n(2,0))
    print(x_n(2,3))
    print(x_n(2,4))

如果面试官询问是否还可以优化？可思考的方向是递归模块提取出来。

def x_n(x,n):
    """
    时间复杂度O(logn)
    """
    if n==0:
        return 1
    t=x_n(x,n//2)
    #print("t:",t)
    if n%2==1:
        return x*t*t
    
    return t*t
if __name__=='__main__':
    print(x_n(2,0))
    print(x_n(2,3))
    print(x_n(2,4))

加载全部内容