江苏龙网

  1. 首页 > 人文 > >

追着幸福跑|Github上复旦小姐姐原创「数据结构和算法系列」


追着幸福跑|Github上复旦小姐姐原创「数据结构和算法系列」一、算法的引入如果 a+b+c=1000 ， 且 a^2+b^2=c^2（a,b,c 为自然数） ， 如何求出所有a、b、c可能的组合?可以用枚举法 ， 简单 ， 但是计算量大 。 需要用至少三个循环来完成 。
import timestart = time.time()for a in range(1001):for b in range(1001):for c in range(1001):if a**2+b**2 == c**2 and a+b+c==1000:print('a = %d,b = %d,c = %d'%(a,b,c))end = time.time()print('The time is %f seconds'%(end-start))运行结果
a = 0,b = 500,c = 500a = 200,b = 375,c = 425a = 375,b = 200,c = 425a = 500,b = 0,c = 500The time is 1317 seconds显然 ， 运行用了很长时间 。 其实 ， 枚举法也是一种算法 ， 该算法的执行次数为1000的三次方 ， 效率很低 。
算法的概念算法是计算机处理信息的本质 。 算法是独立存在的一种解决问题的方法和思想 。 算法的五大特性：输入；输出；有穷性；确定性；可行性 。 对上面程序可以进行一定优化：
import timestart = time.time()for a in range(1001):for b in range(1001-a):c = 1000 - a - bif a**2+b**2 == c**2:print('a = %d,b = %d,c = %d'%(a,b,c))end = time.time()print('The time is %f seconds'%(end-start))运行结果
a = 0,b = 500,c = 500a = 200,b = 375,c = 425a = 375,b = 200,c = 425a = 500,b = 0,c = 500The time is 0.992053 seconds显然比上面的运行时间要短得多得多 。 可以大致得到一个结论：实现算法程序的执行时间可以反应出算法的效率 ， 计算法的优劣 。 算法的效率衡量：执行时间（在一定程度上）反映算法效率 。 但是并不是绝对的 ， 由于：（1）测试结果非常依赖测试环境：硬件不同会对结果造成很大影响 。 （2）测试结果受数据规模和数据本身的影响较大：如对于排序 ， 如数据本身是有序的 ， 可能执行时间就会相对较短 ， 同时数据规模较小时 ， 测试时间不一定能真实反映算法的性能 。 所以每台机器执行总时间不一定一致 ， 但是执行的基本运算的数量大体相同 。
二、时间复杂度大O第一个例子中 ， 执行的次数为：T = 1000 * 1000 * 1000 * 21000到2000时T = 2000 * 2000 * 2000 * 21000换成N时 ， T = n * n * n * 2 = n ^ 3 * 2 = f(n) * 2即T(n) = f(n) * 2T(n) = O(f(n))其中 ， n表示数据规模的大小 ， T(n)表示代码执行的时间 ， f(n)代表每行代码的执行次数总和 ， O表示T(n)与f(n)成正比 。 此即为大O时间复杂度表示法 ， 不是代码真正的执行时间 ， 而是代码执行时间随数据规模增长的变化趋势 ， 也叫渐进时间复杂度 ， 简称时间复杂度 。
三、时间复杂度分析方法：
1.只关心循环执行次数最多的一段代码def cal(n):sum = 0i = 1for i in range(n+1):sum += ireturn sum函数内部 ， 前两行是常量级的执行时间 ， 与n的大小无关 ， 可忽略 ， 关注循环次数最多的那一个即for循环 ， for循环执行了n次 ， 所以时间复杂度为O(n) 。
2.加法原则【追着幸福跑|Github上复旦小姐姐原创「数据结构和算法系列」】总复杂度等于量级最大的那段代码的复杂度 。
def cal(n):sum = 0i = 1for i in range(100):sum += ifor i in range(n+1):sum += ifor i in range(n+1):for i in range(n + 1):pass第一个for循环为常数循环 ， 复杂度为O(1) ， 第二个for为单层循环 ， 为O(n) ， 第三个for循环为双层嵌套循环 ， 时间复杂度为O(n^2) 。 如T(n) = max(O(1),O(n),O(n^2)) = O(n^2) 。 分析算法时 ， 存在几种可能：※最优时间复杂度：最少需要多少基本操作li = [1,2,3,4,5]列表有序 ， 则常数时间 ， O(1) 。 ※平均时间复杂度：平均需要多少基本操作※最坏时间复杂度：最多需要多少基本操作列表无序时 ， 时间复杂度与元素个数正相关 ， 即O(n) 。 最优时间复杂度和平均时间复杂度价值不大 ， 未提供太多有用的信息 ， 因此主要关注算法的最坏情况 ， 亦即最坏时间复杂度 。


推荐阅读


上一篇：莫小帅|土豪的快乐你想象不到！居然为了玩游戏，花30万买了辆车

下一篇：资讯速递号|澳大利亚装起了“傻白甜”，祸到临头才知道急？面对中国的教训