Python算法教程学习笔记_第二章

标签:algorithms, 算法, 笔记

2.2.1渐进记号

  用来表示算法的渐进运行时间的记号是用定义域为自然数集N={0,1,2,…}的函数来定义的这些记号便于用来表示最坏情况运行时间T(n),因为T(n)一般定义于整数的输入规模上。有以下5种:

  • Θ记号 渐进确界
  • ο记号 渐进上界
  • Ω记号 渐进下界
  • º记号 非渐进紧确的上界
  • ω记号 非渐进紧确的下界

2.2.2算法的渐进运行时间(时间复杂度)

  按数量级递增排列,常见的时间复杂度有:

名称 时间复杂度 相关示例及说明
常数阶 Θ(1) 哈希表的查询与遍历
对数阶 Θ(log n) 二分搜索
线性阶 Θ(n) 列表的遍历
线性对数阶 Θ(n log n) 任意值序列的最优化排序
平方阶 Θ(n2) n 个对象相互比较
立方阶 Θ(n3) Floyd-Warshall
多项式级 O(nk) 基于 n 的 k 层嵌套循环(其中K为整数),且必须满足常数k>0
指数阶 Ω(kn) 每 n 项产生一个子集(其中k=2),且必须满足k>1
阶乘级 Θ(n!) 对 n 个只看进行全排列操作

2.3图与树的实现

  图结构(graph) 算法学中最强大框架之一。在许多情况下,我们都可以把一个问题抽象为一个图,如果能抽象为一个图的话,那么该问题至少已经接近解决方案了。如果问题实例可以用树(tree)诠释的话,那么我们基本上已经拥有了一个真正有效的的解决方案了。 下面是一些关于图的术语:

  • 图 G = (V,E) 通常由一组节点 V 及节点间的边 E 共同组成。如果这些边有方向,就称其为有向图。
  • 节点之间通过边来实现彼此相连的。而这些边其实就是节点 v 与其邻居之间的关系。
  • G = (V,E] 的子图结构将由 V 和 E 的子集共同组成。在 G 中,每一条路径(path)是一个子图结构,它们本质上都是一些由多个节点串联而成的边线序列。环路(cycle)的定义与路径基本相同,只不过它的最后一条边所连接的末节点同是是它的首节点。
  • 如果我们将图 G 中的边与某种权值联系在一起,G 就成了一种加权图。在加权图中,一条路径或环路的长度等于各边上的权值之和,对非加权图来说,就直接等于该图的边数。
  • 森林 (forest) 可以被认为是一个无环路图,而这样的连通图就是一棵树。换言之,森林就是由一棵或多棵树构成的。

2.3.1邻接列表及其类似结构

  对于图结构的实现来说,邻接列表是最直观的方式之一。 接下来,我们就要用数据结构来表示图。

2-3

Written on 2019-01-09
上篇: Python算法教程学习笔记_第一章
下篇: HTML5中a标签的download属性