Python 算法之一

Wu_Candy

发布于 2022-07-04 17:47:42

4760

什么是算法

“算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。” “在谈到算法时，我们不得不去了解一下什么是时间复杂度和空间复杂度这两个概念” 计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间,时间复杂度常用大O符号（大O符号（Big O notation）是用于描述函数渐进行为的数学符号。空间复杂度：它是用来评估算法内存占用大小的一个式子。

Python 算法的几大重要特征

有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
确切性（Definiteness）：算法的每一步骤必须有确切的定义；
输入项（Input）：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
输出项（Output）：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
可行性（Effectiveness）：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）；
高效性（High efficiency）：执行速度快，占用资源少；
健壮性（Robustness）：对数据响应正确。

Python算法除了具有以上特征，还和时间和空间有关系，不同的算法可能用不同的时间、空间或效率来完成同样的任务，因此，一个Python算法的优劣可以用空间复杂度与时间复杂度来衡量。

通过实例加深对算法的理解

如题所示：要求x,y,z的1000以内取值满足xx+yy=z*z，同时x+y+z=1000,求解出所以x,y,z的组合情况？

求解过程如下 这里使用了一个waste_time方法作为装饰器来计算装饰过的方法的执行时间，这里有两种算法来求解这个问题

代码如下：

import time
def waste_time(func):
def function(*args,**kwargs):
        start_time=time.time()
        result=func(*args,**kwargs)
        end_time=time.time()
        spend=end_time-start_time
        print("函数%s 总共耗时%.3f秒:"%(func.__name__,spend))
return result
return function

#通常解法--算法1
@waste_time
def normal():
for x in range(1001):
for y in range(1001):
for z in range(1001):
if(x*x+y*y==z*z and x+y+z==1000):
                    print("x=",x,"y=",y,"z=",z)

#改进后解法--算法2
@waste_time
def goodjob():
    for x in range(1001):
        for y in range(1001):
            z=1000-x-y #这里的x,y 已经明确后，那么z就可以直接算出来，而不用放在循环中去遍历
            if(x*x+y*y==z*z):
                print("x=", x, "y=", y, "z=", z)

#入口方法
if __name__ == '__main__':
 print("game start!")
 normal()
 goodjob()
 print("game over!")

响应结果如下：

game start!
x= 0 y= 500 z= 500
x= 200 y= 375 z= 425
x= 375 y= 200 z= 425
x= 500 y= 0 z= 500
函数normal 总共耗时341.505秒:
x= 0 y= 500 z= 500
x= 200 y= 375 z= 425
x= 375 y= 200 z= 425
x= 500 y= 0 z= 500
函数goodjob 总共耗时0.388秒:
game over!

总结： 通过这个示例，对于同一个问题给出两种不同的算法，两种算法在执行过程中我增加了对程序执行时间的统计，通过时间上的对比发现两个算法的执行时间相差非常的大，如响应结果所示。

由此我们可以得出一个结论，就是实现不同的算法程序执行的时间可以反应出算法的效率，即算法有优劣之分，好的算法可以节约时间，提高效率，反之则不然。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-08-31，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法