[算法] 大O记号 RAM 级数

本文根据清华大学邓俊辉老师课程《数据结构》总结，课程地址 。

RAM 寄存器

RAM（Random Access Machine 寄存器），和图灵机（TM）一样，RAM模型也是一半计算工具的简化与抽象。

每一基本操作仅需常数时间：寄存器读写（赋值）、四则运算、比较、goto、call、return。

**通过RAM使我们可以独立于具体的平台，对算法的效率进行比较与评判。**对算法给出客观的评判，而不依赖 平台、编程语言等因素。

算法运行时间 → 算法需要智行的基本操作次数
T(n) = 算法在 RAM 中为求解规模为 n 问题所需的基本操作次数（Times）

大O记号

上面给出了 T(n)，在输入规模 n 足够大时，计算成本的增长方式可以用另一种方式： big‐O notation 表示，
$$\begin{gathered} T(n)=O(f(n)) \\ iff\exists c>0，当n\gg 2后，T(n)<c\times f(n) \end{gathered}$$

常系数可忽略：$O(f(n))=O(c\cdot f(n))$
低次项可忽略：$O(n^a+n^b)=O(n^a),a>b>0$

此外，还有其他记号 $\Omega$ 、$\Theta$，
$
T(n) = \Omega(f(n)) ; \exists c > 0，当n ≫ 2后，T(n) > c \times f(n)
$
$
T(n) = \Theta(f(n)) ;\exists c_1>c_2 > 0，当n ≫ 2后，c1 \times f(n) > T(n) > c2 \times f(n)
$

[2‐SubSet] 例子

【问题描述】 S为一组共n个正整数，$\sum S=2m$ 是否有S的子集T满足$\sum T=m$？

上面的描述与下面例子一致，
【选举人制】总统由各州议会 选出的选举人团选举产生，而 不是由选民直接选举产生50个州加1个特区共 538 票获 270 张选举人票即当选。若共有两位候选人 是否可能各得 269 票？

直觉上解决这一问题，可以逐一检查 S 的每一子集，也就是需要迭代 $2^n$ 轮。实际上，这种算法已经是最优的了。

2‐SubSet 是 NP‐complete 的

就目前的计算模型而言，不存在可在多项式时间内回答此问题的算法

级数

几个比较常见的级数，最好记住。

算数级数：与末项平方同阶
$T(n) = 1+2+ … +n = \frac{n(n+1)}{2} = O(n^2)
$

幂方级数：比幂次高出一阶

几何级数（a>1）：与末项同阶

收敛级数
$1/1/2+1/2/3+1/3/4+...1/(n‐1)/n=1‐1/n<1=O(1)$

$1 + 1/22 + … + 1/n2 < 1 + 1/22 + … = \pi^2/6 = O(1)
$

调和级数
$h(n) = 1 + 1/2 + 1/3 + … + 1/n = \Theta(log\ n)
$

对数级数
$log1 + log2 + log3 + … + logn = log(n!) = \Theta(n·log\ n) $