《数据结构与算法分析》C语言描述

目录

引论

本书讨论的内容

书内容

• 数据结构：主要研究组织大量数据的方法
• 算法分析：对算法运行时间的评估
• 学习要求：中的程序的程序设计知识、离散数学的某些知识

数学知识复习

指数

$$\begin{aligned} X^AX^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} \end{aligned}$$

对数

$$\begin{aligned} \log_AB&=\frac{\log_CB}{\log_CA};~C>0\\~\\ \log AB&=\log A+\log B\\~\\ \log A/B&=\log A-\log B\\~\\ \log(A^B)&=B\log A\\~\\ logX&<X（对所有X>0成立）\\~\\ \log_2 1 &=0，\log_22=1，\log_2 1024=10，\log_2 1048576=20 \end{aligned}$$

级数

级数（类比等比数列求和）

$$\begin{aligned} \sum_{i=0}^N 2^i&=2^{N+1}-1\\ \sum_{i=0}^N A^i&=\frac{A^{N+1}-1}{A-1}\\~\\ 第二个公式中&，若0<A<1，则：\\ \sum_{i=0}^N A^i&\leq\frac{1}{1-A}\\ \lim_{N\rightarrow \infty}\sum_{i=0}^N A^i&=\frac{1}{1-A} \end{aligned}$$

算术级数（类比等差数量求和）

$$\begin{aligned} \sum_{i=1}^N i&=\frac{N(N+1)}{2}\approx \frac{N^2}2\\ \sum_{i=1}^N i^2&=\frac{N(N+1)(2N+1)}{6}\approx \frac{N^3}3\\ \sum_{i=1}^N i^k&\approx \frac{N^{k+1}}{|k+1|}（k\neq-1，等于0是为下一条公式）\\ \sum_{i=1}^N \frac1i &=H_N（调和数）\approx \ln N；~其中误差趋向于欧拉常数~\gamma\approx0.57721566, \end{aligned}$$

一般的代数运算

$$\begin{aligned} \sum_{i=1}^N f(N)&=Nf(N)\\ \sum_{i=n_0}^N f(i)&=\sum_{i=1}^N f(i)-\sum_{i=1}^{n_0-1}f(i) \end{aligned}$$

模运算

如果N整除$(A-B)$，那么我们就说A与B模N同余（congruent），记为$A\equiv B(mod~N)$

即无论A还是B除以N，余数相同，比如$81\equiv61\equiv1(mod~10)$

证明方法

• 归纳法
• 反证法

递归简论

递归的四个基本法则

• 基本情形（base case）。必须有某些基准情形，它们不用递归就能求解
• 不断推进（making progress）。对于那些需要递归求解的情形，递归调用必须能够朝着产生基准情形的方向推进
• 设计法则（design rule）。假设所有递归调用都能运行
• 合成效益法则（compound interest rule）。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复的工作（应该用for）

数学根据是归纳法