Skip to content

二、算法分析

什么是算法分析

程序和算法的区别

  • 算法是对问题解决的分步描述
  • 程序则是采用某种编程语言实现的算法。

同一个算法,通过不同编程语言的不同编写方式,可以产生很多程序。

算法分析的概念

算法分析,主要是从计算资源消耗的角度,来评判和比较算法。

能够更高效利用计算资源,或者更少占用计算资源的算法,就是好算法。

计算资源指标

什么是计算资源呢?

一种是算法解决问题过程中,需要的存储空间或内存

存储空间收到问题自身数据规模的变化影响,要区分哪些存储空间是问题本身描述所需,哪些是算法占用,并不容易。

另一种是算法的执行时间

可以通过对程序进行实际运行测试,获得真实的运行时间

Tips

  • python 的 time 模块,在算法开始、结束时,分别记录系统时间,求其差值即可获得运行时间。
  • 最好能多次运算,求均值。

运行时间检测的分析

程序运行的实际时间,会受到不同编程语言及实际运行环境差异的影响。因此,需要用更好的方法来衡量算法运行时间。

而这个指标,需要与具体的机器、程序、运行时段都无关。

大O表示法

算法时间度量指标

一个算法所实施的操作数量,或者步骤数可以作为独立于具体程序/机器的度量指标。

赋值语句 同时包含了(表达式)计算和(变量)存储两个基本资源。

Tips

其实,除了与计算资源无关的定义语句外,主要就是三种控制流语句和赋值语句,而控制流仅仅起了组织语句的作用,并不实施处理。

赋值语句执行次数

问题规模影响算法执行时间

问题规模——影响算法执行时间的主要因素。

算法分析的目标——找出问题规模会怎样影响一个算法的执行时间。

数量级函数 Order of Magnitude

  • T(n) 的精确值并不是特别重要,重要的是 T(n) 中起决定性因素的主导部分

数量级函数,描述了 T(n) 中随着 n 增加而增加速度最快的主导部分。

Note

称作大O表示法,记作 O(f(n)), 其中 f(n) 表示 T(n) 中的主导部分。

确定运行时间数量级大O的方法

影响算法运行时间的其他因素

  • 有时候,决定运行时间的不仅是问题规模,某些具体数据也会影响算法运行时间
  • 分为最好、最差、和平均情况,平均状况体现了算法的主流性能

常见的大O数量级函数

  • 当 n 较小时,难以确定其数量级
  • 当 n 增到较大时,容易看出其主要变化量级

Tips

共有七种主要的大O数量级函数

f(n) 名称
1 常数
log(n) 对数
n 线性
n*log(n) 对数线性
n^2 平方
n^3 立方
2^n 指数

其他算法复杂度表示法

  • 大O表示法:所有上限中,最小的那个上限。
  • 大欧米茄表示法:所有下限中,最大的那个下限。
  • 大希尔塔表示法:如果上下限相同,可用此表示法。

变位词判断问题(上)

变位词判断问题

问题描述

所谓“变位词”是指两个词之间存在组成字母的重新排列关系。如 heart 和 earth。

解法一:逐字检查

解法二:排序比较

变位词判断问题(下)

解法三:暴力法

解法四:计数比较

Python 数据类型的性能(上)

Python 数据类型的性能

对比 list 和 dict 的操作

list 列表数据类型

list 列表数据类型常用操作性能

4种生成前n个整数列表的方法

使用timeit 模块对函数计时

4种生成前n个整数列表的方法计时

List 基本操作的大O数量级

Python 数据类型的性能(下)

list.pop 的计时试验

dict 数据类型

list 和 dict 的 in 操作对比

更多 python 数据类型操作复杂度