看起来不同, 但解决同一个问题的程序, 哪个更好?
程序和算法有什么区别?
算法是对问题解决的分步描述
程序则是采用某种编程语言实现的算法, 同一个算法通过不同的程序员采用不同的编程语言, 能产生很多程序
举个简单的例子, 下面是做白菜炖粉条的步骤:
五花肉切片, 入油锅煸炒至出油, 略微焦黄, 再放入葱姜八角煸炒一下
将白菜洗净切好, 先将白菜梆放入翻炒片刻, 再放入白菜叶继续翻炒
倒入味极鲜, 蚝油, 加盐, 放入泡好的香菇, 顺便将泡香菇的香菇水一并倒入(不喜香菇的话, 只需倒入水即可), 盖上锅盖炖 10 分钟
将泡好的粉条放入锅中, 翻炒至粉条入味变软
撒入鸡精(也可不放), 即可盛盘出锅
以上的步骤就相当于一个算法
而程序就就相当于将白菜炖粉条做出来,
下面, 我们来看一段程序, 实现从 1 到 n 的累加, 输出总和:
设置累计变量 = 0
从 1 到 n 循环, 逐次累加到累计变量
返回累计变量
- def sumOfN(n):
- theSum = 0
- for i in range(1, n+1):
- theSum = theSum + i
- return theSum
- print(sumOfN(10))
再看第二段程序, 是否感觉怪怪的?
- def foo(tom):
- fred = 0
- for bill in range(1, tom+1):
- barney = bill
- fred = fred + barney
- return fred
- print(foo(10))
其实, 本程序与上一段程序解决的问题是一样的, 这段程序失败在于:
变量命名
有无用的垃圾代码
比较程序的好坏, 有更多因素, 如: 代码风格可读性等等但现在, 我们更感兴趣的是算法本身特性
算法分析主要就是从计算资源消耗的角度来评判和比较算法
更高效利用计算资源, 或者更少占用资源的算法, 就是好算法从这个角度来看, 前述两段程序实际上是基本相同的, 它们都采用了一样的算法来解决累计求和问题
计算资源指标
什么是计算资源?
一种是解决问题过程中需要的存储空间或内存, 但存储空间受到问题自身数据规模的变化影响(如, 给 10000 个整数排序和给 1000000 个整数排序显然不同), 要区分哪些存储空间是问题本身描述所需, 哪些是算法占用并不容易
另一种是算法的执行时间, 我们可以对程序进行实际运行测试, 获得真实的运行时间
运行时间检测
累计求和程序的运行时间检测:
如果累加到 100000:
看起来运行时间增加到 10000 的 10 倍
进一步累加到 1000000:
运行时间有时 100000 的 10 倍了
第二种无迭代的累计算法:
利用求和公式的无迭代算法
采用同样的方法检测运行时间
需要关注的两点
这种算法的运行时间比前种都短很多
运行时间于累计对象 n 的大小没有关系(前种算法是倍数增长关系)
新算法运行时间几乎与需要累计的数目无关
运行时间检测的分析
观察一下第一种迭代算法:
包含了一个循环, 可能会执行更多语句, 这个循环运行次数和累加值 n 有关系, n 增加, 循环次数也增加
但关于运行时间的实际检测, 有点问题, 编程语言和运行环境会影响程序的实际运行时间
同一个算法, 采用不同的编程语言编写, 放在不同的机器上运行, 得到的运行时间会不一样, 有时候会大不一样: 比如把非迭代算法放在老旧机器上跑, 甚至可能慢过新机器上的迭代算法
所以我们需要更好的方法来衡量算法的运行时间, 这个指标与具体的机器程序运行时段, 与编译器都无关
大 O 表示法(Big-O)
一个算法所实施的操作数量或步骤数可作为独立于具体程序 / 机器的度量指标
哪种操作跟算法的具体实现无关?
需要一种通用的基本操作来作为运行步骤的计量单位
赋值语句是一个合适的选择
一条赋值语句同时包含了 (表达式) 计算和 (变量) 存储两个基本资源
仔细观察程序设计语言特性, 除了与计算资源无关的定义语句之外, 主要就是三种控制流语句和赋值语句, 而控制流仅仅起了组织赋值语句的作用, 并不实施处理
分析 SumOfN 的赋值语句数量
对于问题规模 n
赋值语句数量 T(n)=1+n
大 O 表示法(Big-O)
问题规模影响算法执行时间
在前 n 个自然数累计求和的算法中, 需要累计的自然数个数合适作为问题规模的指标前 100000 个自然数求和对比前 1000 个自然数求和, 算是同一问题的更大规模
算法分析的目标是要找出问题规模会怎么影响一个算法的执行时间
数量级函数(Order of Magnitude function)
基本操作数量函数 T(n)的精确值并不是特别重要, 重要的是 T(n)中起决定性因素的主导部分用动态的眼光看, 就是当问题规模增大的时候, T(n)中的一部分会盖过其它部分的贡献数量级函数描述了 T(n)中随着 n 增加而增加速度最快的部分称作大 O 表示法, 记作 O(f(n)), 其中 f(n)表示 T(n)中的主导部分
确定运行时间数量级大 O 的方法
常见的大 O 数量级函数
通常当 n 较小时, 难以确定其数量级;
当 n 增长到较大时, 容易看出其主要变化量级;
从代码分析确定执行时间数量级函数
如下代码:
代码赋值语句可以分为 4 个部分
数量级为:
以上
来源: http://www.jianshu.com/p/4fb94da6adb8