当前位置：首页 > news >正文

第1章引论

news 2025/9/16 0:37:02

前言

这一章，阐述本书的目的，并简要复习离散数学以及程序设计的一些概念：

看到程序在较大输入情况下的运行性能与在适量输入情况下的运行性能具有同等重要性
总结本书其余部分所需要的数学基础
简要复习递归

1.1 本书讨论的内容

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

1.2 数学知识复习

本节列出一些需要记住或是能够推导出的基本公式，复习基本的证明方法

1.2.1 指数

$eq?%5Cmathit%7BX%5E%7BA%7DX%5E%7BB%7D%3DX%5E%7BA+B%7D%7D$

$eq?%5Cmathit%7B%5Cfrac%7BX%5E%7BA%7D%7D%7BX%5E%7BB%7D%7D%3DX%5E%7BA-B%7D%7D$

$eq?%5Cmathit%7B%28X%5E%7BA%7D%29%5E%7BB%7D%3DX%5E%7BAB%7D%7D$

$eq?%5Cmathit%7BX%5E%7BN%7D+X%5E%7BN%7D%3D2X%5E%7BN%7D%5Cneq%20X%5E%7B2N%7D%7D$

$eq?%5Cmathit%7B2%5E%7BN%7D+2%5E%7BN%7D%3D2%5E%7BN+1%7D%7D$

1.2.2 对数

在计算机科学中，除非有特别的声明，所有的对数都是以2为底的

定义：当且仅当 $eq?%5Cmathit%7Blog_%7BX%7DB%3DA%7D$ ， $eq?%5Cmathit%7BX%5E%7BA%7D%3DB%7D$

由该定义得到几个方便的等式：

定理1.1

$eq?%5Cmathit%7Blog_%7BA%7DB%3D%5Cfrac%7Blog_%7BC%7DB%7D%7Blog_%7BC%7DA%7D%7D$ ； $eq?%5Cmathit%7BC%3E0%7D$

定理1.2

$eq?%5Cmathit%7BlogAB%3DlogA+logB%7D$

其他有用的公式

$B%3DlogA-logB%7D$

$eq?%5Cmathit%7Blog%28A%5E%7BB%7D%29%3DBlogA%7D$

$eq?%5Cmathit%7BlogX%3CX%7D$ （对所有的 $eq?%5Cmathit%7BX%3E0%7D$ 成立）

$eq?%5Cmathit%7Blog1%3D0%7D$ ， $eq?%5Cmathit%7Blog2%3D1%7D$ ， $eq?%5Cmathit%7Blog1024%3D10%7D$ ， $eq?%5Cmathit%7Blog1048576%3D20%7D$

1.2.3 级数

几何级数

$eq?%5Cmathit%7B%5Csum_%7Bi%3D0%7D%5E%7BN%7D2%5E%7Bi%7D%3D2%5E%7BN+1%7D-1%7D$

$eq?%5Cmathit%7B%5Csum_%7Bi%3D0%7D%5E%7BN%7DA%5E%7Bi%7D%3D%5Cfrac%7BA%5E%7BN+1%7D-1%7D%7BA-1%7D%7D$

$eq?%5Cmathit%7B%5Csum_%7Bi%3D0%7D%5E%7BN%7DA%5E%7Bi%7D%5Cleqslant%20%5Cfrac%7B1%7D%7B1-A%7D%280%3CA%3C1%29%7D$

收敛级数

$eq?%5Cmathit%7B%5Csum_%7Bi%3D0%7D%5E%7B%5Cinfty%20%7DA%5E%7Bi%7D%280%3CA%3C1%29%3D%5Cfrac%7B1%7D%7B1-A%7D%7D$

$2%5E%7Bi%7D%3D2%7D$

算数级数

$eq?%5Cmathit%7B%5Csum_%7Bi%3D1%7D%5E%7BN%7Di%3D%5Cfrac%7BN%28N+1%29%7D%7B2%7D%5Capprox%20%5Cfrac%7BN%5E%7B2%7D%7D%7B2%7D%7D$

$eq?%5Cmathit%7B%5Csum_%7Bi%3D1%7D%5E%7BN%7Di%5E%7B2%7D%3D%5Cfrac%7BN%28N+1%29%282N+1%29%7D%7B6%7D%5Capprox%20%5Cfrac%7BN%5E%7B3%7D%7D%7B3%7D%7D$

$eq?%5Cmathit%7B%5Csum_%7Bi%3D1%7D%5E%7BN%7Di%5E%7Bk%7D%5Capprox%20%5Cfrac%7BN%5E%7Bk+1%7D%7D%7B%5Cleft%20%7C%20k+1%20%5Cright%20%7C%7D%7D$ ； $eq?%5Cmathit%7Bk%5Cneq%20-1%7D$

数 $eq?%5Cmathit%7BH_%7BN%7D%7D$ 叫作调和数，其和叫作调和和。以下近似式中的误差趋向于 $eq?%5Cmathit%7B%5Cgamma%20%5Capprox%200.57721566%7D$ ，这个值称为欧拉常数（Euler's constant）

$eq?%5Cmathit%7BH_%7BN%7D%3D%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Cfrac%7B1%7D%7Bi%7D%5Capprox%20log_%7Be%7DN%7D$

代数运算

$eq?%5Cmathit%7B%5Csum_%7Bi%3D1%7D%5E%7BN%7Df%28N%29%3DNf%28N%29%7D$

$eq?%5Cmathit%7B%5Csum_%7Bi%3Dn_%7B0%7D%7D%5E%7BN%7Df%28i%29%3D%5Csum_%7Bi%3D1%7D%5E%7BN%7Df%28i%29-%5Csum_%7Bi%3D1%7D%5E%7Bn_%7B0%7D-1%7Df%28i%29%7D$

1.2.4 模运算

如果N整除A-B，那么我们就说A与B模N同余(congruent)，记为A=B(mod N)。直观地看，这意味着无论A还是B除以N，所得余数都是相同的。于是，81=61=1(mod 10)。如同等号的情形一样，若A=B(mod N)，则A+C=B+C(mod N)以及AD=BD(mod N)。
有许多定理适用于模运算，其中有一些特别要用到数论来证明。我们将谨慎地使用模运算，这样，前面的一些定理也就足够了。