0206：数据结构-大O表示法
本文依照学习难度，分成入门、进阶两个部分。
入门部分以直观、易于理解为主；进阶部分重点在于概念、推导等。
目录
入门
在使用算法时，总是会提及性能好、速度快，那么如何度量好与快呢？
使用 O(n)，n为操作数
大O表示法让你能够比较操作数，它指出了算法运行时间的增速
关键词：操作数、增速
比如，在查找算法里，同样是在N个数里查找元素
简单查找和二分查找有这样的差异
|---------------------+------------+-----------------|
| 简单查找 | 二分查找 |
|---------------------|:-----------|:---------------:|
| 100个元素 | 100毫秒 | 7毫秒 |
| 10,000个元素 | 10秒 | 14毫秒 |
| 1000,000,000个元素 | 11天 | 32毫秒 |
|---------------------+------------+-----------------|
可以看到随着元素个数的增加，差距越来越大。
有鉴于此，仅知道算法需要多长时间才能运行完毕还不够，还需要知道运行时间如何随列表增长而增加
特别注意的是，O(n)里面的n并不是指以秒为单位的速度，而是执行的操作数量。
为啥是n次呢，也可能第一个就找到了，O(n)是按照最糟糕情形来计算的，也就是n个元素，最后一个才找到自己想要的
O(n) 和 O(logn) 区别在哪里
目前使用大O表示法，log指的都是log2
一些常见的大O运行时间 O(logn):对数时间，例如：二分查找 O(n):线性时间，例如：简单查找 O(nlogn):例如：快速排序 O(n^2):例如：选择排序 O(n!):例如：旅行商问题
看电话簿里每个人的名字，需要n次，只看其中的A开头，O(n)并不会变成O(n/26)，而依旧是O(n)
因为在很多情况下，常量无关紧要，比如
但有时候，常量的影响很大，例如在快速查找、合并查找情形下。
运行时间：
取决于输入
如果输入序列已经有序，那插入排序需要做的工作就很少了
如果输入序列是逆序，那情况最糟糕，需要大量的工作，不得不把所有元素的都整理一遍
取决于输入规模
规模越大，运行时间就越长，因此把输入规模参数化，把运行时间看做待排列数据规模的函数
一般想知道运行时间的上限，也就是想知道运行时间是不会超过某个特定量的。这代表了对用户的一种承诺。
告诉你：运行时间至少3s和最多3s，意义完全不一样
对算法有各种各样的分析，其中一种叫做“最坏情况分析”
此时，T(n)定义为输入规模为n时的最长运行时间，是一个函数关系，而不是相关关系。因为它需要将输入，最大化输出出来，一一对应。
有时候，也会讨论“平均情况”
这时，T(n)就是输入规模n下所有可能输入的期望时间。
这里期望指的是：每种输入的运行时间乘以那种输入出现的概率
但是一般不知道这个概率是多少 ==> 做假设（做假设需要符合哪些条件呢？） ==> 一个有关输入的统计分布的假设
最常见的假设之一就是：所有输入都是以等可能方式出现的，即所谓均匀分布
也有“最好情况假设”，一般人们喜欢把最好情况称为“假象”
因为一个人研发出了一个很慢速的算法，但是他拿最好的情况做说明，更像是一种欺骗行为了。
有人说，那运行速度也很受硬件设备的影响。
因此，在比较算法的时候，通常比较的是其相对速度，也就是假设两个算法在同一台机器上。
进阶
[1] 算法图解 Aditya Bhargava (作者) 袁国忠 (译者)