Python递归时间复杂度

目录
  • 思路一：for循环
  • 思路二：递归

递归也是常见算法之一，其时间复杂度一般认为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))

到此这篇关于Python递归时间复杂度的文章就介绍到这了,更多相关Python递归内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • python递归&迭代方法实现链表反转

    python递归&迭代方法实现链表反转

    定义链表node结构: class ListNode:       def __init__(self,data):         self.data = data         self.next = None 将L转化为链表: def make_list(L): 将L初始化为链表:   head = ListNode(L[0])     cur = head     for i in L[1:]:         cur.next = ListNode(i)         cur =

  • turtle的基础使用之python turtle递归绘图

    turtle的基础使用之python turtle递归绘图

    目录 1创建窗口 2.画笔移动 3.递归画图 1创建窗口 1 turtle.setup(width,height,startx,starty)设置主窗口的大小和位置, width如果是整数,则以像素为单位的大小,如果是浮点数,则屏幕的一部分:默认为屏幕的 50%. height 如果是整数,则以像素为单位的高度,如果是浮点数,则为屏幕的一部分:默认为屏幕的 75% startx 如果为正,则从屏幕左边缘开始以像素为单位,如果从右边缘为负,如果没有,则水平居中窗口 starty如果为正,则从屏幕上

  • python数据结构之递归方法讲解

    python数据结构之递归方法讲解

    目录 1.递归概念 2. 递归三原则 2.1 实现任意进制的数据转换 今天我们来学习python中最为重要的内容之递归,对以往内容感兴趣的同学可以查看下面: python数据类型: python数据结构:数据类型. python的输入输出: python数据结构之输入输出.控制和异常. python面向对象: python数据结构之面向对象. python算法分析: python数据结构算法分析. python数据结构之栈.队列和双端队列 递归是在进行重复性工作中经常考到的问题,非常值得学习.

  • Python 函数的递归详解

    Python 函数的递归详解

    目录 1.1.递归函数的特点 1.2 递归案例 ----- 计算数字累加 总结 函数调用自身的 编程技巧 称为递归. 1.1.递归函数的特点 特点: 一个函数 内部 调用自己. 函数内部可以调用其他函数,当然在函数内部也可以调用自己. 代码特点: 1).函数内部的 代码 是相同的,只是针对 参数 不同,处理的结果不同: 2).当 参数满足一个条件 时,函数不再执行: 这个非常重要,通常被称为递归的出口,否则 会出现死循环! def sum_number(num): print(num) # 递归

  • Python 递归式实现二叉树前序,中序,后序遍历

    Python 递归式实现二叉树前序,中序,后序遍历

    目录 1.前序遍历 2.中序遍历 3.后序遍历 4.测试 5.结果 6.补充 6.1N叉树前序遍历 记忆点: 前序:VLR 中序:LVR 后序:LRV 举例: 一颗二叉树如下图所示: 则它的前序.中序.后序遍历流程如下图所示: 1.前序遍历 class Solution:     def preorderTraversal(self, root: TreeNode):              def preorder(root: TreeNode):             if not ro

  • Python递归时间复杂度

    目录 思路一:for循环 思路二:递归 递归也是常见算法之一,其时间复杂度一般认为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 __na

  • python 递归遍历文件夹,并打印满足条件的文件路径实例

    题目:利用协程来遍历目录下,所有子文件及子文件夹下的文件是否含有某个字段值,并打印满足条件的文件的绝对路径. #!/user/bin/env python # -*- coding:utf-8 -*- #grep -rl "python" D:\devtools\workspace\python\aaa import os def init(func): def wrapper(*args,**kwargs): res=func(*args,**kwargs) res.send(Non

  • Python递归遍历列表及输出的实现方法

    本文实例讲述了Python递归遍历列表及输出的实现方法.分享给大家供大家参考.具体实现方法如下: def dp(s): if isinstance(s,(int,str)): print(s) else: for item in s: dp(item) l=['jack',('tom',23),'rose',(14,55,67)] dp(l) 运行结果如下: jack tom 23 rose 14 55 67 希望本文所述对大家的Python程序设计有所帮助.

  • python递归打印某个目录的内容(实例讲解)

    以下函数列出某个目录下(包括子目录)所有文件,本随笔重点不在于递归函数的实现,这是一个很简单的递归,重点在于熟悉Python 库os以及os.path一些函数的功能和用法. 1. os.listdir(path): 列出path下所有内容(包括文件和目录,不包括.和..) 2. os.path.join(path1,path2,path3...): 拼接目录,例如将'home','test'拼接成'home/test/' 3. os.path.isdir(path): 判断path是否为目录 代

  • python递归删除指定目录及其所有内容的方法

    实例如下: #! /usr/bin/python # -*- coding: utf-8 -*- import os def del_dir_tree(path): ''' 递归删除目录及其子目录, 子文件''' if os.path.isfile(path): try: os.remove(path) except Exception, e: #pass print e elif os.path.isdir(path): for item in os.listdir(path): itempa

  • Python递归实现汉诺塔算法示例

    本文实例讲述了Python递归实现汉诺塔算法.分享给大家供大家参考,具体如下: 最近面试题,面试官让我5分钟实现汉诺塔算法(已然忘记汉诺塔是啥). 痛定思痛,回来查了一下汉诺塔的题目和算法.题干与实现如下: A基座有64个盘子,大在下小在上,每次移动一个盘子,每次都需要大在下小在上,全部移动到B基座,C基座为辅助基座. # -*- coding:utf-8 -*- # 汉诺塔回溯递归实现 # 假设参数中初始杆为a,借助杆为c,阶段终止杆为b # 第一步,a状态借助b移动到c # 第二步,a移动到

  • python递归全排列实现方法

    本文实例为大家分享了python递归全排列的实现方法,供大家参考,具体内容如下 排列:从n个元素中任取m个元素,并按照一定的顺序进行排列,称为排列: 全排列:当n==m时,称为全排列: 比如:集合{ 1,2,3}的全排列为: { 1 2 3} { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 2 1 } { 3 1 2 } 递归思想: 取出数组中第一个元素放到最后,即a[1]与a[n]交换,然后递归求a[n-1]的全排列 1)如果数组只有一个元素n=1,a={1} 则全排列就是

  • python 递归深度优先搜索与广度优先搜索算法模拟实现

     一.递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! (2)# 写递归的过程 1.写出临界条件 2.找出这一次和上一次关系 3.假设当前函数已经能用,调用自身计算上一次的结果,再求出本次的结果 (3)案例分析:求1+2+3+...+n的数和 # 概述 ''' 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! ''' # 写递归的过程 ''' 1.写出临界条件 2.找出这一次和上一次关系 3.假设

  • Python递归及尾递归优化操作实例分析

    本文实例讲述了Python递归及尾递归优化操作.分享给大家供大家参考,具体如下: 1.递归介绍 递归简而言之就是自己调用自己.使用递归解决问题的核心就是分析出递归的模型,看这个问题能拆分出和自己类似的问题并且有一个递归出口.比如最简单的就5的阶乘,可以把它拆分成5*4!,然后求4!又可以调用自己,这种问题显然可以用递归解决,递归的出口就是求1!,可以直接返回1.用Python实现如下: def fact(n): if n==1: return n return n*fact(n - 1); pr

  • Python递归调用实现数字累加的代码

    我就废话不多说了,直接上代码吧! def sum_numbers(num): # 1.出口 if num == 1: return 1 # 2.数组累加 temp = sum_numbers(num - 1) return num + temp result = sum_numbers(3) print(result) 输出: 6 补充拓展:python递归计数及结束递归 题目:搜索旋转排序数组 class Solution: TOTAL = 0 RUN = True def search(se

随机推荐