代数和几何知识介绍

5.1.1　对数函数及其应用

1．对数函数简介

若a^b＝N（a＞0，a≠1），则b叫做以a为底N的对数，记作b＝log_aN。当a＝10时称作常用对数，当a＝e时称作自然对数。

16世纪末17世纪初在自然科学领域，特别是天文学方面经常遇到十分复杂的数值计算。数学家们为了寻求化简计算的方法而发明了对数。一般认为，对数是由苏格兰数学家纳皮尔和瑞士工程师比尔吉彼此独立地发明的。但在此之前，在法国数学家许凯（15世纪）和德国数学家施蒂费尔（1487—1567年）的工作中就已经孕育了对数的思想，他们研究等比数列与等差数列之间的关系，特别是施蒂费尔将这两种数列加以对比，并指出：等比数列各项的乘、除、乘方、开方运算，相当于等差数列相应各项的加、减、乘、除运算。但是他们都没有进一步发展这种思想。

比尔吉是瑞士的一位工程师，他曾担任著名天文学家开普勒的助手，因此经常接触复杂的天文计算，于是产生了化简数值计算的强烈愿望。他受施蒂费尔工作的影响，考虑等差数列

0，10，20，…，10n

和与之对应的等比数列

由此建立了一种对数体系，于1620年发表在《等差数列和等比数列表》中。不难看出，比尔吉所造的对数表，把对数的底取为（1.0001）¹⁰⁴，与现在自然对数的底e相差甚小。

比尔吉约于1610年发明对数，但他推迟了发表的时间，而纳皮尔的对数表在1614年公之于世，早比尔吉6年。纳皮尔是苏格兰的一个贵族，他对数值计算颇有研究。他制造的“纳皮尔算筹”化简了乘除法运算，其原理就是用加减法来代替乘除法。纳皮尔发明对数的动机是为寻求球面三角计算的简便方法，他依据一种非常独特的与质点运动有关的设想构造出所谓对数方法，其核心思想表现为算术数列与几何数列之间的联系。在他的《奇妙的对数表的描述》中阐明了对数原理，后人称他发明的对数为纳皮尔对数，记为Nap·log x，它与自然对数的关系为

现在通用的以10为底的常用对数，是由英国数学家布里格斯首先采用的，在他1624年出版的《对数算术》中，载有14位的常用对数表。他还制作了正弦、正切对数表。荷兰数学家兼出版商弗拉克补充了布里格斯的对数表，他出版的几种对数表（包括三角函数对数表）很快在欧洲普及。弗拉克还最早阐明对数首数的意义。

关于以e为底的自然对数的准确含义，是由英国数学教师斯佩德尔（J.Speidell）首先指出的，他在1619年出版了关于对数的著作，包含1～1000的自然对数表。

2．对数的基本运算法则（以下运算默认底数相同）

log a＋log b＝log（ab）

log a－log b＝log（a/b）

n×log a＝log（aⁿ）

换底公式：

log_ab／log_ac＝log_cb

log_ab×log_ca＝log_cb

3．对数的考察范围

认识对数函数、理解对数函数的意义。

【例5-1】一棵完全二叉树共有N个节点，这棵完全二叉树的深度是多少？

A．log N

B．log N＋1

C．［log N］

D．［log N］＋1

（以上对数均以2为底，［x］表示不超过x的最大整数）

答案：D

5.1.2　从平面向量到空间向量

既有方向又有大小的量叫做向量（物理学中叫做矢量），只有大小没有方向的量叫做数量（物理学中叫做标量）。

1．平面向量

具有方向的线段叫做有向线段，以A为起点，B为终点的有向线段记作AB。

有向线段AB的长度叫做向量的模，记作∣AB∣。

有向线段包含3个因素：起点、方向、长度。

长度相等且方向相同的向量叫做相等向量。两个方向相同或相反的非零向量叫做平行向量，向量a、b平行，记作a∥b，零向量与任意向量平行，即0∥a，在向量中共线向量就是平行向量。这和直线不同，直线共线就是同一条直线了，而向量共线就是指两条是平行向量。长度等于0的向量叫做零向量，记作0。（实数“0”和向量“0”是有区别的）零向量的方向是任意的；且零向量与任何向量都垂直。长度等于1个单位长度的向量叫做单位向量。

2．平面向量的坐标表示

在直角坐标系内，我们分别取与x轴、y轴方向相同的两个单位向量i、j作为基底。任作一个向量a，有且只有一对实数x、y，使得a＝x_i＋y_j。

我们把（x，y）叫做向量a的（直角）坐标，记作a＝（x，y），其中x叫做a在x轴上的坐标，y叫做a在y轴上的坐标，上式叫做向量的坐标表示。

在平面直角坐标系内，每一个平面向量都可以用一对实数唯一表示。另一方面，从点A（x₁，y₁）到点B（x₂，y₂）的向量可以用坐标表示为（x₂－x₁，y₂－y₁）。

3．向量的数量积

（1）向量数量积定义。

①向量A与向量B的夹角：已知两个非零向量，过O点做向量OA＝a，向量OB＝b，则角AOB＝θ叫做向量A与B的夹角。

②已知两个非零向量a、b，那么∣a∣∣b∣cosθ叫做a与b的数量积或内积或点积，记作a·b，θ是a与b的夹角，∣a∣cosθ（∣b∣cosθ）叫做向量a在b方向上（b在a方向上）的投影。零向量与任意向量的数量积为0。

注意：向量数量积的结果是一个数，而不是一个向量。

③a·b的几何意义：数量积a·b等于a的长度∣a∣与b在a的方向上的投影∣b∣cosθ的乘积。两个向量的数量积等于它们对应坐标的乘积的和。即：若a＝（x₁，y₁），b＝（x₂，y₂），则a·b＝x₁x₂＋y₁y₂。

（2）向量的数量积的性质。

①a·a＝∣a∣²≥0；

②a·b＝b·a；

③k（ab）＝（ka）b＝a（kb）；

④a·（b＋c）＝a·b＋a·c；

⑤a·b＝0⇔a⊥b

⑥a＝kb⇔a∥b

⑦e₁·e₂＝∣e₁∣∣e₂∣cosθ＝cosθ

4．推论

两个向量垂直等价于它们的数量积为0。

5．三维坐标系中的扩展——空间向量

三维空间中的有向线段称为向量，它同样可以用3个与x轴、y轴、z轴同向的单位向量i、j、k作为基底，每个空间向量都唯一地表示为a＝x_i＋y_j＋z_k，用坐标写就是a＝（x，y，z）。

空间向量同样有数量积的概念，若a＝（x₁，y₁，z₁），b＝（x₂，y₂，z₂），则a·b＝x₁x₂＋y₁y₂＋z₁z₂。

在三维空间中，数量积的推论也成立，即两个向量垂直等价于它们的数量积为0。与某个平面垂直的向量至少与这个平面上两个不平行的向量垂直。

6．例题（2010年第十六届全国青少年信息学奥林匹克联赛初赛提高组不定项选择题）

【例5-2】一个平面的法线是指与该平面垂直的直线。过点（1，1，1）、（0，3，0）、（2，0，0）的平面的法线是　　　　　（　　）

A．过点（1，1，1）、（2，3，3）的直线

B．过点（1，1，1）、（3，2，1）的直线

C．过点（0，3，0）、（－3，1，1）的直线

D．过点（2，0，0）、（5，2，1）的直线

答案：D

5.1.3　时间复杂度分析与最优排序

1．时间复杂度

我们常说的时间复杂度实际上是指渐进时间复杂度，我们更多地关心一个算法在数据规模扩大时随数据规模而增加的速度，并不是对一个特定的数据所消耗的时间。

2．记号说明

大O表示法：记f（n）＝O（g（n））表示存在常数N和c，对于n≥N时，总有f（n）≤c·g（n）成立，事实上意味着f（n）的增长速度不超过g（n）。

3．常见排序算法的时间复杂度

（1）冒泡排序、选择排序、插入排序为O（N²）。

希尔排序的时间复杂度见表5-1。

表5-1　希尔排序时间复杂度

（3）快速排序的平均O（nlog n），最坏情况下O（n²）。

（4）归并排序、堆排序为O（nlog n）。

需要注意的是，由于递归调用需要消耗一定的时间，在实际运用的过程中，对不超过20个数排序可以使用冒泡而不是快速排序。

另一方面，对于快速排序，一般的选取枢纽元的方法。例如，取第一个数、取中间的那个数都可能导致最坏情况，但是有一些特定的算法可以保证在O（n）或O（1）的时间内选取枢纽元并且保证快速排序的时间复杂度平均和最坏都为O（nlog n），读者可参阅相关选取枢纽元算法的资料。

4．时间复杂度的分析

快速排序和归并排序用到了分治算法。在分治算法中，设T（n）表示解决规模为n的问题所需的时间，如果我们能用O（n）的时间使T（n）缩减为kT（n/c），k和c是常数，那么我们可以得出结论T（n）＝O（nlog n）。例如，快速排序的平均情况和归并排序，我们是在O（n）的时间内使问题规模缩小为一半，即T（n）＝2T（n/2）＋O（n）。如果我们能用O（n）的时间使T（n）缩减为kT（n－c），k和c，是常数，那么我们可以得出结论T（n）＝O（n²），如快速排序的最坏情况。

5．基于非比较的排序算法

最常见的基于非比较的排序算法是基数排序，它在对不超过长整型的数进行排序时可以认为理论时间复杂度是O（n），但在具体的实践中，所选取的基数也不宜过大，尤其不能大于数据的个数，否则基数排序便失去了它的优势。

6．最少比较排序

【例5-3】（2006年全国青少年信息学奥林匹克联赛初赛普及组单项选择题）

对于一个有5个元素的数组，最少需要几次比较才能保证数组有序？　　　　（　　）

A．5次

B．6次

C．7次

D．8次

答案：C

分析：首先我们证明7次比较是可行的。

引理：2次比较可以将一个未知的元素插入到一个有3个元素的有序数列中并且保证插入完成后数列有序。

引理的证明：设未知元素是x，原始数列为a、b、c，且a＜b＜c，首先将x和b比较大小，不妨设x＜b，然后将x与a比较大小，若x小，则x＜a＜b＜c，否则a＜x＜b＜c；如果x＞b，则将x与c比较大小，与前者同理。引理得证。

回到原问题，不妨设这5个数为a、b、c、d、e，首先比较a、b大小，比较c、d大小，不妨设a＜b，c＜d。接着比较b、d大小，不妨设b＜d，于是，得到一个长度为3的有序数列a＜b＜d，同时知道c＜d，根据引理，用2次比较将e插入到a、b、d这个数列中。由于已知c＜d，于是c最多只与a、b、e三个数未确定相对大小（若e＞d，则c＜d＜e，c与e的相对大小也已经确定了），而且a、b、e这三个数之间的相对大小已确定，不妨设a＜b＜e，根据引理，我们可以用两次比较将c插入到a、b、e这个序列中，又因为已知a、b、c、e都比d小，于是这5个数排序完毕，我们一共用了7次比较。

下面引入决策树的概念说明6次或更少不可能的原因。

决策树一般都是自上而下的来生成的。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。

对于排序事件，每一个不同的状态是一组比较的结果如a＜b，若为真，则会引发一些结果，若为假，又会引发另一些结果，而最终的结果就是这5个元素的相对大小关系，易知共有5！＝120种大小关系，因此决策树的叶子节点一共有120个。

又显然决策树中的每个状态都只有真和假两种可能，故这个决策树是一棵二叉树，而一棵决策树的深度决定了这种排序的比较方法最少要比较多少次才能保证确定这5个数的顺序。因为120＞2⁶，于是深度为6或更少的决策树无法拥有120个叶子节点，即6次或更少的比较次数无法保证确定这5个数的大小关系。

综上，5个元素至少需要7次排序才能保证元素可以被排好序。

一个更一般的问题：对于任意的N，至少需要多少次比较才能保证排好序？令人遗憾的是，这个问题至今没有明确的解答，但是一个根据上文对决策树的分析，一个显然的事实是，比较次数的下限是［log₂N！］≈［Nlog₂N］－N。至于这个下限是否对每个N都能达到，还是一个未知数。更详细更深入的讨论请读者参考Donald E. Knuth的名著《计算机程序设计艺术》（The Art of Computer Programming）第3卷第5章第3节中的《最优排序·极小比较排序》部分。

不过我们可以由此产生一个显然的推论，就是基于比较的排序算法的时间复杂度下限是O（Nlog N）。渐进时间复杂度的计算会忽略低阶函数，于是［Nlog₂N］－N＝O（Nlog N）。

7．最少交换排序

最少交换排序分为两种：①每次只能交换任意的两个数；②每次可以交换相邻两个数。这两种类型的分析见第5.2.7节。