2.1什么是算法分析

作者: M_小七 | 来源:发表于2020-08-13 14:12 被阅读0次

2.1什么是算法分析
缓存分析
算法分析：如何分析一个算法的效率好坏？
算法导论学习笔记（1）
插入排序
算法导论——第一部分基础知识（二）
Java虚拟机之垃圾回收算法
算法分析
算法设计与分析——2.渐进分析与Python计算模型
算法2.1

对比程序，还是算法？

如何对比两个程序？看起来不同，但解决同一个问题的程序，哪个“更好”？

程序和算法的区别：

算法是对问题解决的分步描述
程序则是采用某种编程语言实现的算法，同一个算法通过不同的程序员采用不同的编程语言，能产生很多程序

从简单的例子中理解

1.累计求和问题
完成从1到n的累加，输出总和

设置累计变量=0
从1到n循环，逐次累加到累计变量
返回累计变量

def sum0fN(n):
    theSum = 0
    for i in range(1, n + 1):
        # theSum += i
        theSum = theSum + i
    return theSum
print(sum0fN(10))

再看第二段程序，是否感觉怪怪的？
但实际上本程序功能与前面那段相同
这段程序失败之处在于：变量命名词不达意，以及包含了无用的垃圾代码

def foo(tom):
    fred = 0
    for bill in range(1, tom + 1):
        barney = bill
        fred = fred + barney
    return fred
print(foo(10))

算法分析的概念

算法分析主要就是从计算资源消耗的角度来评判和比较算法
更高效利用计算资源，或者更少占用计算资源的算法，就是好算法
从这个角度，前述两段程序实际上是基本相同的，它们都采用了一样的算法来解决累计求和问题

计算资源指标

一种是算法解决问题过程中需要的存储空间或内存
但存储空间受到问题自身数据规模的变化影响要区分哪些存储空间是问题本身描述所需，哪些是算法占用，不容易
另一种是算法的执行时间
我们可以对程序进行实际运行测试，获得真实的运行时间

运行时间检测

Python中有一个time模块，可以获取计算机系统当前时间
在算法开始前和结束后分别记录系统时间，即可得到运行时间

累计求和程序的运行时间检测
用time检测总运行时间
返回累计和，以及运行时间（秒）

import time
def sum0fN(n):
    start = time.time()
    theSum = 0
    for i in range(1, n + 1):
        # theSum += i
        theSum = theSum + i
    end = time.time()
    return theSum, end - start

for i in range(5):
    print("sum is %d required %10.7f seconds"%sum0fN(10000))

输出结果为

sum is 50005000 required  0.0009620 seconds
sum is 50005000 required  0.0010183 seconds
sum is 50005000 required  0.0009100 seconds
sum is 50005000 required  0.0009131 seconds
sum is 50005000 required  0.0009799 seconds

计算100000的时候

sum is 5000050000 required  0.0103390 seconds
sum is 5000050000 required  0.0091000 seconds
sum is 5000050000 required  0.0082438 seconds
sum is 5000050000 required  0.0078683 seconds
sum is 5000050000 required  0.0081780 seconds

由此可见，随着数量的增加，运行时间也会随之增加

下面来看一下无迭代的累计算法
利用求和公式的无迭代算法

import time
def sum0fN(n):
    start = time.time()
    theSum = (n * (n + 1))/2
    end = time.time()
    return theSum, end - start

for i in range(5):
    print("sum is %d required %10.7f seconds"%sum0fN(100000)

得到结果

sum is 5000050000 required  0.0000019 seconds
sum is 5000050000 required  0.0000007 seconds
sum is 5000050000 required  0.0000010 seconds
sum is 5000050000 required  0.0000000 seconds
sum is 5000050000 required  0.0000000 seconds

这种算法的运行时间比前种都短很多运行时间与累计对象n的大小没有关系（前种算法是倍数增长关系），运行时间几乎与需要累计的数目无关