《数据结构与算法分析》读书笔记（1）

｜第1章引论

1.2 数学知识复习

1.2.1 指数

公式
$X^A X^B = X^{A+B}$
$\frac{X^A}{X^B} = X^{A-B}$
$(X^A)^B = X^{AB}$ $X^N + X^N = 2X^N \neq X^{2N}$
$2^N + 2^N = 2^{N+1}$

1.2.2 对数

公式
$\log_AB = \frac{\log_CB}{\log_CA}; A,B,C>0, A\neq 1$
$\log{AB} = logA + logB; A,B > 0$
$log(A^B) = BlogA$
$logX < X {\quad} 对所有的X > 0均成立$

1.2.3 级数

公式
$\sum_{i=0}^{N}2^i = 2^{N+1} - 1 {\quad} ①$
$\sum_{i=0}^{N}A^i = \frac {A^{N+1}-1}{A-1} {\quad} ②$
证明
- 证明方法主要有： 归纳法，反证法，举反例
- 用归纳法证明公式①(自证，写法可能不严谨)
  $$ \begin{aligned} N=0时, 2^0 =& 2^{(0+1)} - 1 \\\
  =& 2^1 -1\\\
  =& 1 \quad 成立 \end{aligned}\
  $$

$$ \begin{aligned} &假设N=k(为自然数)时仍成立，应满足\\\
&2^0 + 2^1 + ... + 2^k = 2^{k+1} - 1 \quad ・・・①\\\
&N=k+1时，应满足\\\
2^0 +& 2^1 + ... + 2^k + 2^{k+1} = 2^{(k+1)+1} - 1 = 2^{k+2} - 1 \quad ・・・②\\\
& ②-①得：\\\
& 2^{k+1} = (z^{k+2} - 1) - (2^{k+1} - 1) = 2^{k+2} - 2^{k+1}\\\
& => \\\
& 2^{k+1} + 2^{k+1} = 2^{k+2}\\\
& => \\\
& 2 \times 2^{k+1} = 2^{k+2} \quad 显然成立 \\\
&由此可证等式在任意自然数N的情况下均成立 \end{aligned}\
$$

1.2.4 模运算

A与B模N同余： $$ A\equiv B (mod N) $$
含义： N整除A-B，则A、B被N除的余数相同
定理： $$ \begin{aligned} 若{\quad} &A\equiv B (mod N) \\\ 则{\quad} &A+D\equiv B+D (mod N) ,\\\
&AD\equiv BD (mod N) \end{aligned}\
$$

1.3 递归简论

定义：一个函数用它自身来定义时即为递归的
如： $f(x) = 2f(x-1)+x^2; f(0) = 0$
※f(0)为基本情形，没有则毫无意义，因为其他情形均由其递推得出
原则
- 1. 必须有基本情形
- 1. 朝着基本情形不断推进
- 1. 设计法则：假设所有调用都能运行
- 1. 合成效益法则（？）
执行过程：先递再归
如定义中的函数调用过程如下： $$ \begin{aligned} f(x)\stackrel{调用}{\longrightarrow} f(x-1) \stackrel{调用}{\longrightarrow} ... f(2) \rightarrow f(1) \rightarrow f(0) (基本情形，已知为0) \quad 【递】\\\ f(x)\leftarrow f(x-1) \leftarrow ... f(2) \stackrel{计算}{\longleftarrow} f(1) \stackrel{计算}{\longleftarrow} f(0) \quad \hookleftarrow【归】 \end{aligned} $$

1.4-1.5 泛型

java5之前实现泛型构件

用Object表示泛型，问题是8种基本类型不适用。
用接口表示泛型，如Comparable接口保证所有实现该接口的类型可以使用ComparaTo比较大小，包括基本类型的包装类。但无法拓展的final类等不适用。

泛型

类声明中传入的类型参数为泛型时，保证了类内部使用它时类型一致。将用Object表示泛型时可能引起的运行时错误提前到编译时。
自动装箱/拆箱简化了基本类型和包装类之间繁琐的类型转换。
通配符解决了泛型数组的协变性。java中数组是协变的（即数组型参数可以接受具有IS-A关系的其他类的数组）而泛型集合不是。Collection<? extends Super>解决了这点。
类型限界：可指定泛型方法类型参数尖括号内类型的性质，如T extends Interface<? super T>。
类型擦除：编译器在编译时将泛型类转化为非泛型类（原始类）的过程，生成与程序员使用泛型前差不多的代码。

【练习】

Plan

1～2章：顺序阅读+Blog笔记
3章～：先刷题后查找

《数据结构与算法分析》读书笔记（1）

相关文章：