首页 » 开发 » 数据结构与算法

算法

⌊n⌋ - 表示向下取整(直接抹去小数部分)。例如⌊3.1⌋为3。

⌈n⌉ - 表示向上取整(大于等于一个浮点数的最小整数)。例如⌈3.1⌉为4。

渐进符号

几种常用渐进符号的定义:Ο、Ω、Θ、ο、ω。

Ο(g(n)) = { f(n) : 存在常数因子c和n0,使得对所有的n ≥ n0 有 0 ≤ f(n) ≤ cg(n) }

Ω(g(n)) = { f(n) : 存在常数因子c和n0,使得对所有的n ≥ n0 有 0 ≤ cg(n) ≤ f(n) }

Θ(g(n)) = { f(n) : 存在常数因子c1、c2和n0,使得对所有的n ≥ n0 有 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) }

f(n) = Ο(g(n))    ≈ a ≤ b
f(n) = Ω(g(n))    ≈ a ≥ b
f(n) = Θ(g(n))    ≈ a = b
f(n) = ο(g(n))    ≈ a < b
f(n) = ω(g(n))    ≈ a > b

常见的渐进效率类型

类型名称说明
1常量为数极少的高效率算法。
log n对数算法每次循环都会消去问题规模的一个常数因子。
n线性典型的扫描规模为n的列表的算法(如顺序查找)。
n log nn-log-n许多分治算法(如快排、合并排序)的效率。
n2平方典型的两重嵌套循环算法效率。
n3立方典型的三重嵌套循环算法效率。如线性代数中的一些算法。
2n指数求n个元素集合中的所有子集。
n!阶乘求n个元素集合的完全排列算法。

一个对数算法不可能关注它的输入的每一个部分,任何能做到这一点的算法至少也是一个线性算法。鱼书列举了一个有趣的面试问题:打印一棵二叉树的时间复杂度是多少?大多数二叉树操作的复杂度都是Ο(log n),但打印二叉树需要访问每个元素,所以时间复杂度是Ο(n)。

分享

0