Python的算法介绍以及递归的特点 时间复杂度 空间复杂度

鳄鱼君

发表文章数:642

热门标签

, , ,

Vieu四代商业主题

高扩展、安全、稳定、响应式布局多功能模板。

¥69 现在购买
首页 » 经验教程 » Python的算法介绍以及递归的特点 时间复杂度 空间复杂度

什么是算法?算法(Algorithm):一个计算过程,解决问题的方法

递归的两个特点:

  1. 自己调用自己
  2. 存在结束条件

我们看一下下面的函数是否属于递归:

# 没有结束条件
def fun1(x):
    print(x)
    fun1(x-1)
fun1(5)
# 没有结束条件
def fun2(x):
    if x>0:
        print(x)
        fun2(x+1)
fun2(5)
# 递归
def fun3(x):
    if x>0:
        print(x)
        fun3(x-1)
fun3(5)
#5
#4
#3
#2
#1


# 递归
def fun4(x):
    if x>0:
        fun4(x - 1)
        print(x)
fun4(5)

#1
#2
#3
#4
#5

fun3和fun4函数都有结束条件,所以属于递归。两者的区别就在于print的位置不一样,因此打印的结果也不一样,具体的效果可以自己参照代码尝试一下!

时间复杂度

时间复杂度:用来评估算法运行效率的一个东西。评判代码写的好坏,就需要通过时间复杂度。我们通过下面的代码来判断一下时间的复杂度:

O(1)
print("Hello Eyujun!") # print执行了一次

O(n)
for i in range(n):
    print("Hello Eyujun!") # print执行了n次

O(n²)
for i in range(n):
    for j in range(n):
        print("Hello Eyujun!") # print执行了n²次

O(n³)
for i in range(n):
    for j in range(n):
        for k in range(n):
            print("Hello Eyujun!") # print执行了n³次

我们可以通过print执行的次数来判断以上代码的时间复杂度,就是代码的执行效率。我们按照这个方法,再来看一下下面的代码:

O(3)
print("Hello Eyujun!") 
print("Hello World!") 
print("Hello Python!") # print执行了3次

O(n²+1)
# 里面的for循环为O(n) ,外面有一个print,所以0(n+1)
# 外面循环了一层,所以就是0(n(n+1)) 即:O(n²+1)
for i in range(n):
    print("Hello Eyujun!")  # print执行了n次 O(n+1)
    for j in range(n):
        print("Hello Eyujun!") # print执行了n次 O(n)

# i=0 没有print
# i=1 print执行1次 
# i=2 print执行2次
# i=3 print执行3次
# ......
# 相当于99乘法表

O(1/2n²)
for i in range(n):
    for j in range(i):
        print("Hello Eyujun!")

以上代码我们分析的看起来非常正确,但其实全部是错误的!时间复杂度是一个单位,对于第一个,单位不会出现3,print打印3次和1次,看不出来到底谁快,所以通常都估计为O(1);第二个,不会出现+号,相当于舍掉后面的值,就是O(n²);对于第三个,时间复杂度不可能小于1,所以说还是O(n²)

我们再来看一下下面的代码:

O()
while n>1:
    print(n)
    n=n//2 # 整除

我们通过对前面几个例子的判断,大致可以断定,几层循环就是O(n几),上面的代码很明显一层循环,可以断定它的时间复杂度应该是O(n)。我们假设n=64,输出的结果如下:

64
32
16
8
4
2

可以看到。n=64的时候,代码执行了6次,每次数值减少一半,也就是说2的6次方是等于64的,可以用数学的指数来表示:以2为底64的对数等于6,即log₂64,类比以上代码的复杂度就是O(log2n)或O(logn),一般使用后者。

时间复杂度是用来估计算法运行时间的一个式子(单位)。一般来说,时间复杂度高的算法比复杂度低的算法,不考虑机器因素,问题规模相同的情况下。常见的复杂度(按效率排序):

  1. O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n²logn)<O(n³)

前面3个非常好理解,第4个和第5个相比,相当于O(logn)和O(n),即O(nlogn)<O(n²);O(n²)和O(n²logn)相当于O(1)<O(logn),即O(n²)<O(n²logn);O(n²logn)和O(n³)相当于O(logn)<O(n),即O(n²logn)<O(n³)

不常见的时间复杂度:

  1. O(n!)O(2^n)O(n^n) ….(非常慢)

通过以上的联系,我们可以总结出,怎样才能快速的判断出代码的时间复杂度:

  1. 循环减半的过程————》O(logn)
  2. 几次循环就是n的几次方复杂度

空间复杂度

空间复杂度:用来评估算法内存占用大小的一个式子。在函数里面申请几个变量,空间复杂度就是O(1);开一个列表,空间复杂度就是O(n);开一个二维列表,空间复杂度就是O(n²)

未经允许不得转载:作者:鳄鱼君, 转载或复制请以 超链接形式 并注明出处 鳄鱼君
原文地址:《Python的算法介绍以及递归的特点 时间复杂度 空间复杂度》 发布于2020-06-26

分享到:
赞(0) 赏杯咖啡

评论 抢沙发

6 + 8 =


文章对你有帮助可赏作者一杯咖啡

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.6主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
切换注册

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录
切换登录

注册