Python 数据结构与算法 —— 初识算法
算法是什么？ 举个简单例子： 我们要做一份蛋炒饭： 拿钱包，出门，去菜市场购买鸡蛋和大米以及油和盐——购买蛋炒饭的材料 回家将大米淘洗干净放进电饭煲——煮熟大米 将锅放在电磁炉上加热——往锅里倒适量油 将鸡蛋打开放入油锅——翻炒鸡蛋至七分熟 将适量煮熟的米饭倒入锅中，加盐——翻炒两分钟 以上就是制作一份简单蛋炒饭的步骤 如果把这些交给机器来做，也是如此，并且步骤将更加细分和严谨 简单来讲，这就是算法 那么算法到底是什么呢？ 先来看一道简单的高中数学题： 现有a,b,c三个自然数，要求满足以下条件： 1.a+b+c = 1000 2.a^2 + b^2 = c^2 (^代表平方) 分析： 首先排除数学公式，我们使用机器思维来计算这道题，能想到的办法也很简单，即一个一个数尝试 ，直到试出准确答案为止，此种方法我们称之为 枚举法 上面数学题使用Python来实现： import time start_time = time.time() for a in range(0, 1001): for b in range(0, 1001): for c in range(0, 1001): if a+b+c == 1000 and a**2 + b**2 == c**2: print("a, b, c: %d, %d,%d" % (a, b, c)) end_time = time.time() print("time:%d" % (end_time - start_time)) print("finished!") 代码执行结果： C:\python3\setup\python.exe C:/Users/limia/Desktop/DataS/01_枚举组合.py a, b, c: 0, 500,500 a, b, c: 200, 375,425 a, b, c: 375, 200,425 a, b, c: 500, 0,500 time:121 finished! Process finished with exit code 0 注释： 在上面的代码中：计算这道数学题的同时，还引入了time模块来计算这段代码的运行时间，以方便之后对比算法效率 通过分析这道题，我们可以得知，a+b+c=1000，在有了a和b的值之后，c的值自然就可以计算为：1000-a-b，分析至此，则代码可以改进为以下： import time start_time = time.time() for a in range(0, 1001): for b in range(0, 1001): c = 1000 - a -b if a**2 + b**2 == c**2: print("a, b, c: %d, %d,%d" % (a, b, c)) end_time = time.time() print("time:%d" % (end_time - start_time)) print("finished!") 代码执行结果： C:\python3\setup\python.exe C:/Users/limia/Desktop/DataS/01_枚举组合.py a, b, c: 0, 500,500 a, b, c: 200, 375,425 a, b, c: 375, 200,425 a, b, c: 500, 0,500 time:1 finished! Process finished with exit code 0 通过对比，可以一目了然的发现，改进后的代码执行效率（1s）明显高于第一种代码执行效率（121s） 算法的概念： 算法是计算机处理信息的本质 算法是独立存在的一种解决问题的方法和思想 计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务 单纯以时间衡量算法效率是否是科学的、客观的？ 答案：不客观 假设在一台古老的计算机上运行上面的两个程序，则其所消耗的时间都将是极长的，因此单纯以时间计算算法的效率是不科学的。 在衡量算法的效率时，应当脱离计算机来估算 因此引入时间复杂度来衡量算法的效率 每台计算机执行的总时间不同，但是执行基本运算数量大体相同 上面的两个程序，以时间复杂度来表示算法效率： T = 1000 * 1000 * 1000 * 2 ==》 当计算的不是a+b+c=1000，而是a+b+c=2000时，以时间复杂度表示则 T = 2000 * 2000 * 2000 * 2 ==》 当计算的不是1000或者2000,而是n呢？ T(n) = n * n * n * 2 简化： T(n) = n^3 * 2 则此时 **T(n) = n^3 * 2 ** 即为这个程序算法的时间复杂度函数 通过函数 T(n) = n^3 * 2 ,可做出曲线图 系数对曲线形状改变不大，只是陡峭不同，因此 T(n) = n^3 * 2 可以简化为T(n) = n^3 T(n) = n^3 则可以叫做 T(n) = n^3 * 2 的渐进函数 大O表示法 上述 **T(n) = n^3 ** 就是 ** T(n) = n^3 * 2 ** 的大O 表示法 总结： 大O表示法只留下表示特征的部分 常见时间复杂度之间的关系 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) 个人博客地址：www.limiao.tech 微信公众号：TechBoard 慕课网：techLee 如果觉得文章对您有所帮助，那就伸出小手 ==>> 点击下方 [ like ] 吧
