1.1 为什么要学它(Motivation)
1.2 High level idea
1.3 4个例子
2. Big-Oh Notation
2.1 文本定义
2.2 图形定义
2.3 数学定义
3. 2个例子
3.1 k阶多项式是O(n^k)
3.2 k阶多项式不是O(n^(k-1))
4. Big Omega and Theta
4.1 Big-Omega表示法
4.2 Big-theta表示法
4.3 Little-O表示法
4.4 渐进性表示法的来源
5. 几个额外的例子【可选】
5.1 在指数中添加一个常数
5.2 指数乘以一个常数
5.2 最大值和求和
1. The Gist
1.1 为什么要学它(Motivation)我们的目的是寻找一种对算法进行衡量的最有效力度，我们希望忽略不重要的细节，例如常数因子和低阶项，把注意力集中在算法的运行时间是怎样随着输入长度的增长而增长的，这些任务是通过大O表示法(包括它的近亲表示法)的形式完成的，每个程序员都应该掌握这个概念。
它是行业术语渐进性表示法提供了讨论算法设计与分析的基本术语，当我们听到某个程序员谈论他的某段代码以"n的大O时间运行"，而另一段代码，以"n平方的大O时间运行"时，我们需要知道其中的意思。它是区别不同算法的"sweet spot"它有粗放和精细的两个特征。粗放:忽略了所以我们想要忽略的细节，比如说计算机体系结构，具体选择的编程语言以及编译器等方面的细节。精细:可以在不同层次对解决这个问题不同算法进行比较，尤其在巨大输入情况下，输入的规模越大，就越需要精妙的算法。
1.2 High level idea一句话概括渐进性表示法的话，就是忽略常数因子和它的低阶项。
为什么我们要忽略常数因子和它的低阶项？根据定义，我们把注意力放在大规模的输入时低阶项的作用就几乎可以忽略了，而大规模的输入才是需要精妙算法的时候，同时常数因子一般高度依赖于环境的细节，如果我们分析算法时并不想固定于某种特定语言计算机体系结构和编译器，那么使用不在意的常数因子就会非常合理。不是说忽略的就不重要，什么时候它重要？忽略的意思并不是说常数因子是完全无关紧要的，只不过当我们想要对解决同一个问题的一些不同方法进行比较的时候，渐进性表示法往往是正确的工具，它能帮助我们理解哪种算法的性能最佳，尤其是当输入规模非常大时，但我们确定了某个问题的最佳高级算法后，可能还想进一步优化常数因子和低阶项。
1.3 4个例子这里有4个比较简单的例子，如果是第一次接触这个概念的朋友可以自己试着做一下，求每个例子的渐进性运行时间。后台回复【渐进性表示法】查看答案。Algorithm 1数组A中包含整数t吗？
1: for i = 1 to n do 2: if A[i] == t then 3: Return TRUE 4: Return FALSE