第二章笔记：计数初步

摘要：1.求和的概念2.求和问题3.子集和排列组合4.递归与递归式

1.求和式的含义

 ∑ 即数学含义。（略）

2.求和（组合）问题

2.1握手问题

n(n-1)/2       Θ(n²)   握手次数 地图上各点距离的比较次数 （等差数列）

2.2龟兔赛跑

淘汰赛制 n-1 ,  1+2+4+8+...+n/2 (或 2^h-1)   令2^h=n

任何一个几何级（或指数级）的数列都是kⁱ(其中i=0,...,n,k为常数)的一个求和式。如果k>1，该求和式复杂度始终为Θ(kⁿ⁺¹)。倍增式序列的求和式只是一个特例。

下面 龟兔赛跑问题：兔子和乌龟分别代表了树结构的高度和宽度。宽度 n = 2^h，高度 h = lgⁿ。

如何弄清楚两者间的巨大差异，要么 超理想的对数级算法，要么 不可行的指数级算法。

3.子集与排列组合问题

 初等数学

4.递归与递归式

第二章笔记：计数初步

原文：https://www.cnblogs.com/vangaohao/p/11374663.html