定性研究与定量研究
定量研究与定性研究是社会科学领域两种对立的研究范式，两者在研究目标、对象及方法上都存在着明显的区别。
首先，研究目标上，定量研究重视预测控制，而定性研究重视对意义的理解；
其次，研究对象上，定量研究强调事实的客观实在性，而定性研究强调对象的主观意向性；
第三，研究方法上，定量研究注重经验证实，而定性研究注重解释建构。
由于方法论上的不同取向，导致了在实际应用中定量研究与定性研究存在明显的差别。这主要体现在如下几个方面：
- 着眼点不同
定量研究着重事物量的方面；定性研究着重事物质的方面。
- 在研究中所处的层次不同
定量研究是为了更准确地定性。
- 依据不同
定量研究依据的主要是调查得到的现实资料数据，定性研究的依据则是大量历史事实和生活经验材料。
- 手段不同
定量研究主要运用经验测量、统计分析和建立模型等方法；定性研究则主要运用逻辑推理、历史比较等方法。
- 学科基础不同
定量研究是以概率论、社会统计学等为基础，而定性研究则以逻辑学、历史学为基础。
- 结论表述形式不同
定量研究主要以数据、模式、图形等来表达；定性研究结论多以文字描述为主。定性研究是定量研究的基础，是它的指南，但只有同时运用定量研究，才能在精确定量的根据下准确定性。
如何评估算法性能
如何评估一个算法的性能？什么是大 O 表示法
评估算法性能：
- 主要评估问题的输入规模 n 和元素的访问次数 f(n) 的关系
- f(n) = n
- f(n) = n2 或 f(n) = 2n2 + n + 5
大 O 符号：忽略非主体部分，如常数项、低阶项
- O(g(n)) = { f(n) ：存在正常数 c 和 n0 ，使对所有 n >= n0 ，有 0 <= f(n) <= cg(n) }
- O(g(n))，表示这个算法是有一个 渐近上界 的，这个渐近上界为 g(n)，算法的运行时间 f(n) 趋近并小于等于这个 g(n)
知道算法的时间复杂度之后，我们可以计算每秒能够处理的数据规模。
- n! 的弱上界是 n ^ n，因此增长速度非常快，这意味着单位时间内可求解的问题很小，换言之，超慢
- 2^n 这样的指数函数增长非常快，这种算法可以认为超慢
- O(n2) 和 O(n3) 增长很快，算法很慢，至少优化到 nlgn，O(n2) 的有冒泡排序、直接插入排序、选择排序
- nlgn 可以认为是及格的算法，一般分治法可以缩小层数为 lgn，而每层的复杂度一般为 O(n)，例如归并排序算法、快速排序算法
- O(n) 叫做线性算法，这种算法比较优秀，或者问题本身比较简单，比如连续求和最大子数组的线性解
- O(sqrt(n)) 比 O(n) 更快，但是这种算法很少
- lgn 就是很优秀的算法了，比如二分查找法，但是这种算法往往对输入数据的格式是有要求的，二分查找要求输入数据有序
- 还有一种是常量，无论规模怎么扩大，都花固定时间，这是为数极少的效率最高的算法了，多数是数据很规则
2 的幂表
| 2 的幂 | 准确值（X） | 近似值 | X 字节转换为 MB、GB 等 |
|---|---|---|---|
| 7 | 128 | ||
| 8 | 256 | ||
| 10 | 1024 | 一千 | 1K |
| 16 | 65 536 | 64KB | |
| 20 | 1 048 576 | 一百万 | 1MB |
| 30 | 1 073 741 824 | 十亿 | 1GB |
| 32 | 4 294 967 296 | 4GB | |
| 40 | 1 099 511 627 776 | 一万亿 | 1TB |
有了这张表就可以做速算：例如，一个将每个 32 位整数映射为布尔值的散列表可以一台普通的计算机的内存（4GB）填满。
经典算法分析：n 与 lgn
- 顺序查找：O(n)
- 二分查找：O(lgn)
经典算法分析：n2 与 nlgn
- 冒泡、插入、选择排序
- Array.sort()
三种典型递归形式算法性能分析
看两个问题：
- 子问题的规模下降
- 子问题求解答案消耗的时间
先看基础的：
- 阶层
- 递推公式：f(n) = n * f(n - 1)
- 子问题规模下降：n -> n * (n - 1) 忽略常数得 T(n - 1)
- 处理子问题：O(1)
- 总结：T(n) = T(n - 1) + O(1) 下降一次消耗的时间是线性时间
- 共要下降 n 次，F(n) = n * T(n) = O(n)
- 总结：阶层递归的时间复杂度是 O(n)
- 递推公式：f(n) = n * f(n - 1)
再看复杂的：
- 汉诺塔递归形式算法分析
- 和斐波那契类似都是 O(2n)
- 斐波那契数列递归形式算法分析
- 递推公式：f(n) = f(n - 1) + f(n - 2)
- 子问题下降规模：n - > (n -1) 和 n -> (n - 2) 两者用的时间是一样，可以合并：n -> 2(n - 1)
- 处理子问题：O(1)
- 一次子问题规模下降需要的时间：T(n) = 2T(n - 1) + O(1)
- 斐波那契数列递归形式比较特殊，规模下降是成等比数列：2、4、8、16 …… 即 2n
- 总结斐波那契数列递归的时间复杂度：F(n) = 2n * T(n) = O(2n)
- 最大公约数算法分析
- 辗转相除法
- 等价替换：f(m, n) = f(n, m % n)
- 子问题规模下降：(m, n) -> (n, m%n)，这里利用了一个数学上的知识点：
- m -> n
- n - > m % n
- ….
推导：前置条件 m > n
| 次数 | m | n | 数学性质 |
|---|---|---|---|
| 1 | n | m%n | m%n < n/2 |
| 2 | m%n | n%(m%n) | n%(m%n) < (m%n)/2 < n/2 |
| 3 | n%(m%n) | (m%n)%(n%(m%n)) | (m%n)%(n%(m%n)) < n%(m%n)/2 < n/4 |
| 4 | … | … | … < n/4 |
| 5 | … | … | … |
| 6 | … | … | …<n/8 |
| … | … | … | … |
我们可以从定性的角度去研究这个问题，可以推出每下降两次，n 就会减半一次。
次数 x 和结果的关系： 结果 = n/2x/2
我们知道递归的出口是 n = 1，那么当 n 降低 1 时需要多少次呢？
1 = n/2x/2
两边同时取对数最后化简可得近似值 x = 2lgn
所以递归调用 2lgn 次（小技巧：这里的 2 是因为每隔两次下降一半），递归就可以结束了
（注意：正常情况下 lg 是以 10 为底，log 需要指定底数，但是在计算机学界，2 作为底数比较常见，所以这里的 lg 指的是以 2 为底，同样 logn 也是以 2 为底数）
综上：最大公约数辗转相除法的时间复杂度可以表示为 O(lgn)
评估递归算法的时间复杂度
| 递归关系 | 结果 | 举例 |
|---|---|---|
| T(n) = T(n/2) + O(1) | T(n) = O(logn) | 二分查找，欧几里得 GCD |
| T(n) = T(n - 1) + O(1) | T(n) = O(n) | 线性查找 |
| T(n) = 2T(n/2) + O(1) （特例） | T(n) = O(n) | |
| T(n) = 2T(n/2) + O(n) | T(n) = O(nlogn) | 归并、快排 |
| T(n) = 2T(n/2) + O(nlogn) | T(n) = O(nlog2n) | |
| T(n) = T(n - 1) + O(n) | T(n) = O(n2) | 选择排序、插入排序 |
| T(n) = 2T(n - 1) + O(1) | T(n) = O(2^n) | 汉诺塔 |
| T(n) = T(n - 1) + T(n - 2) + O(1) | T(n) = O(2^n) | 递归的斐波那契 |
希尔排序的性能分析
- 如果原始数据的大部分元素已经排序，那么插入排序的速度很快（因为需要移动的元素很少）
- 为什么 “快”？
- 无序的时候，元素少
- 元素多的时候，已经基本有序
原理：在增量不断缩小的过程中，增量产生的子序列的个数越来越少，子序列中元素的数量越来越多，但是元素越来越有序
刚开始：子序列多，但是子序列中元素的数量少
后来：子序列少，但是子序列中元素的数量多
- 最好与最坏
由于希尔排序的特点，我们不太好进行评估算法性能，这时我们可以从最好和最坏两个角度去看
排序算法的稳定性
- 稳定：如果 a 原本在 b 的前面，而 a = b，排序之后 a 仍然在 b 的前面
- 不稳定：如果 a 原本在 b 的前面，而 a = b，排序之后 a 可能会出现在 b 的后面
