江苏龙网

  1. 主页 > 生活百科 > >

Github上复旦小姐姐原创「数据结构和算法系列」

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 - b        if 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 = 0    i = 1    for i in range(n+1):        sum += i        return sum函数内部，前两行是常量级的执行时间，与n的大小无关，可忽略，关注循环次数最多的那一个即for循环，for循环执行了n次，所以时间复杂度为O(n) 。
2.加法原则总复杂度等于量级最大的那段代码的复杂度 。
def cal(n):    sum = 0    i = 1    for i in range(100):        sum += i    for i in range(n+1):        sum += i    for i in range(n+1):        for i in range(n + 1):            pass


推荐阅读


上一篇：对于内存结构的简单理解

下一篇：十分钟掌握数据分析及可视化基本操作