爱抄书读书每天一个知识点

数据结构与算法分析 —— C 语言描述：引论

2022-03-15 本文已影响0人 Sun东辉

在许多问题当中，一个重要的观念是：写出一个可以工作的程序并不够。如果这个程序在巨大的数据集上运行，那么运行时间就变成了重要的问题。我们将在本书中看到对于大量的输入如何估计程序的运行时间，尤其是如何在尚未具体编码的情况下比较两个程序的运行时间。我们还将看到彻底改进程序速度以及确定程序瓶颈的方法。这些方法将使我们能够找到需要大力优化的那些代码段。

数学知识复习

指数

$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\;\;!=\;X^{2N}$

$2^N\;+\;2^N\;=\;2^{N+1}$

对数

定义：当且仅当 $\log_AB\;=\;A,\;X^A\;=\;B$ 。推导可得：

$\log_AB\;=\;\frac{\log_CB}{\log_CA};\;C\;>\;0$

$\log AB\;=\;\log\;A\;+\;\log\;B$

$\log\;\frac AB\;=\;\log\;A\;-\;\log\;B\\$

$\log\left(A^B\right)\;=\;B\;\log\;A$

$\log\;X\;<\;X(\mathrm{对所有的}\;X>0\mathrm{成立})$

$\log\;1\;=\;0,\;\log\;2\;=\;1,\;\log\;1024\;=\;10,\;\log\;1048576\;=\;20$

级数

$\sum_{i\;=\;0}^N2^i\;=\;2^{N+1}\;-\;1$

如果 0 < A < 1

$\sum_{i\;=\;0}^NA^i\;=\frac1{1\;-\;A}$

否则

$\sum_{i\;=\;0}^NA^i\;=\frac{A^{N+1}\;-\;1}{A\;-\;1}$

模运算

如果 N 整除 A - B，那么我们就说 A 与 B 模 N 同余（congruent），记为 $A\equiv B$ (mod N)。直观地看，这意味着无论 A 还是 B 除以 N，所得余数都是相同的。于是， $81\;\equiv\;61\;\equiv\;1(mod\;10)$ 。如同等号的情形一样，若 $A\equiv B$ (mod N)，则 $A+\;C\equiv B\;+\;C(mod\;N\;)$ 以及 $AD\equiv BD(mod\;N\;)$ 。

证明方法

归纳法证明：第一步是证明基准情形（base case），就是确定定理对于某个（某些）小的（通常是退化的）值的正确性，这一步几乎总是很简单的。接着，进行归纳假设。一般来说，这意味着假设定理对直到某个有限数 k 的所有情况都是成立的。然后使用这个假设证明定理对下一个值（通常是 k + 1）也是成立的。至此定理得证（在 k 有限的情形下）。
- 定理：如果 $N\geq1$ ，则 $\sum_{i=1}^Ni^2\;=\;\frac{N(N+1)(2N+1)}6$ 。
通过反例证明：反证法证明是通过假设定理不成立，然后证明该假设导致某个已知的性质不成立，从而说明原假设是错误的。

递归简论

递归的四条基本法则

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

上一篇下一篇

猜你喜欢

热点阅读