渐近记号
θ(g(n))={f(n):存在正常数c1,c2和n0,使对所有的n>=n0,有0 <= c1g(n) <= f(n) <= c2g(n)}
Ο(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)}
o(g(n))={f(n):对任意正常数c,存在常数n0>0,使对所有的n>=n0,有0 <= f(n) < cg(n)}
ω(g(n))={f(n):对任意正常数c,存在常数n0>0,使对所有的n>=n0,有0 <= cg(n) < f(n)}
传递性
f(n) = θ(g(n)) 和 g(n) = θ(h(n)) 蕴含f(n) = θ(h(n))
f(n) = Ο(g(n)) 和 g(n) = Ο(h(n)) 蕴含f(n) = Ο(h(n))
f(n) = Ω(g(n)) 和 g(n) = Ω(h(n)) 蕴含f(n) = Ω(h(n))
f(n) = o(g(n)) 和 g(n) = o(h(n)) 蕴含f(n) = o(h(n))
f(n) = ω(g(n)) 和 g(n) = ω(h(n)) 蕴含f(n) = ω(h(n))
自反性
f(n) = θ(f(n)) f(n) = Ο(f(n)) f(n) = Ω(f(n))
对称性
f(n) = θ(g(n)) 当且仅当 g(n) = θ(f(n))
转置对称性
f(n) = Ο(g(n)) 当且仅当 g(n) = Ω(f(n))
f(n) = o(g(n)) 当且仅当 g(n) = ω(f(n))
类比
f(n) = Ο(g(n)) ~ a <= b
f(n) = Ω(g(n)) ~ a >= b
f(n) = θ(g(n)) ~ a = b
f(n) = o(g(n)) ~ a < b
f(n) = ω(g(n)) ~ a > b
标准记号和常用函数
函数f(n)单调递增:若m <= n蕴含f(m) <= f(n)
函数f(n)单调递减:若m <= n蕴含f(m) >= f(n)
函数f(n)严格递增:若m < n蕴含f(m) < f(n)
函数f(n)严格递减:若m < n蕴含f(m) > f(n)
下取整和上取整:x-1 < [_ x _] <= [- x -] < x+1
取模: a mod n = a - [_a/n_]n
多项式:给定一个正整数d,n的d次多项式是具有如下形式的函数p(n):
d
p(n) = ∑ ain^i
i=0
指数式:对任意实数a>0、m和n,有下列恒等式:
a^0 = 1, a^1 = a, a^-1 = 1/a
(a^m)^n = a^mn, (a^m)^n = (a^n)^m, a^ma^n = a^m+n
对数:
lgn = log2n
lnn = logen
lg^kn = (lgn)^k
lglgn = lg(lgn)
阶乘:
记号n!定义为对所有整数n >= 0,
n! { 1 如果n=0
n*(n-1)! 如果n > 0
函数迭代:
f(i)(n) = { n 如果i=0
f(f(i-1)(n)) 如果i>0
多重对数函数:
lg*n = min{i >= 0: lg(i)n <=1}
斐波那契数:
斐波那契数递归地定义为:
F0 = 0, F1 = 1, Fi = Fi-1 + Fi-2 当i >= 2
分享到:
相关推荐
CLRS 最后,要拿 LeetCode,Python 可以让你专注于想法,而 CLRS 真的有点乏味,所以每当你读完时,你就会感到很高兴,因为你可以做 LeetCode。 :books: :open_book: :pencil: :notebook: :hamburger: :spaghetti: :...
算法简介第3版 托马斯·科门(Thomas H.Cormen) 查尔斯·莱森(Charles E.Leiserson) 罗纳德·里维斯特(Ronald Rivest) 克利福德·斯坦
CLRS(Introduction.to.Algorithms.Second.Edition)
CLRS教材练习算法关于该项目重点在于通过在代码中实现对基本和高级数据结构及算法的掌握。 这主要是在Python中完成的。促成主题分叉项目创建功能分支( git checkout -b feature/AmazingFeature ) 提交更改( git ...
clrs-notes-solutions, 算法导论,第3版,学习笔记,习题答案
CLRS英文第二版 .
在有关算法的书中,有一些叙述非常严谨,但不够全面;另一些涉及了大量的题材,但又缺乏严谨性。《算法导论(原书第3版)》将严谨性和全面性融为一体,深入讨论各类算法,并着力使这些算法的设计和分析能为各个层次的...
一个个人帮助页面,用于准备数据结构和算法,重点是CLRS书籍... /src目录是添加各种算法的实现的位置。 该README.md文件用于列出数据结构和算法,而不一定来自本书。 快速浏览 目录 Sl。 话题 1。 :check_box_...
CLRS CLRS 代码
算法导论CLRS 英文第3版 pdf 是算法方面的经典著作
大名鼎鼎的 CLRS Algorithm Introduction 算法导论 课后大部分的题目解答
算法导论 CLRS Mit Press - Introduction To Algorithms 2Nd Edition Incl Exercises Edition.chm
指《算法导论》(Introduction to Algorithms)。 由Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein编写,MIT出版的一本介绍、分析当代计算机...用四位作者姓的首字母组成的CLRS代表此书。
算法导论 CLRS 英文第三版 算法导论 CLRS 英文第三版
CLRS CLRS示例代码的C ++实现和研究目的。 不涉及编码的练习将不会共享。
CLRS Problems 15-5 的解法
clrs CLRS算法的实现
MIT算法分析教材CLRS的教师手册,内有课程精讲及习题答案
algorithms from CLRS "Introduction to Algorithms 3rd" implementation in C++ templates. 《算法导论》第三版 C++泛型实现
CLRS-Solutions, "Introduction to Algorithm, 3rd Edition" 解决方案 解决方案介绍,3rd 版"下载最新解决方案?下载在这里网页上可用的 。还提供了上一个版本。:如何编译它?$ git clone git@github....