对数函数总结

对数函数在复杂度计算中是一类非常重要的函数，我对其基本性质做了些基本的概括。

在比较函数的阶时，我们通常会按照阶的高低分为以下三类：

类型	例子
至少指数级	2n ，n！， nn …
多项式级	n，2n，nlogn， n300 …
对数多项式级	logn， logn10， logloglogn…

从此出可见对数函数的重要性，在复杂度比较中基本上都会涉及到对数函数的运用。

对数函数的定义的引入

首先我们通过乘除运算来引出对数函数的定义，在数学中，若我们是以乘法为正运算，则除法为逆运算，而对于指数运算，它的逆运算则为对数运算，反之亦然。

举个例子，

• 对于乘法运算式 4 * 5 = 20，其逆运算为 20 / 5 = 4 或者 20 / 4 = 5；
• 对于乘幂运算 4⁵=1024，其逆运算为 log4(1024) = 5

上面第二个例子意味着一个数字的对数是必须产生另一个固定数字（基数）的指数。

对数符号及其严格定义

从严格定义来讲，若 N = a^x （a>0，a≠1），即 a 的 x 次方等于 N（a>0，且a≠1），那么我们称数 x 叫做以 a 为底 N 的对数（logarithm）。

常常记作 x = log a(N)，其中a叫做对数的底数，N叫做真数，x叫做“以a为底N的对数。

（ 注意由于0的任何次方均为0，所以0没有对数）

对数函数的定义

y = log a(x) 其中 x 为自变量，x的定义域是（0，+∞），y为因变量。

函数图像过定点（1，0），即x=1时，y=0。

当 a ∈ （0，1）时函数为减函数；当 a ∈ （1，+∞）时函数为增函数；a = 1时函数不存在。

以 2 为底的对数函数图像如下，

从图中我们也可以看见，对数函数的增长是非常缓慢的。

对数函数的一些性质以及常用对数

常用对数

1. 我们将以自然常数 e 为底的对数函数常记作 y = ln x ;
2. 而以 10 为底的对数函数记作 y = lg x ;
3. 由于算法复杂度分析中有些算法会常常使用二分法，所以常常在复杂度分析中，我们会省略 y = log 2 (x) 中的底数2，而直接记作 y = log x 。

函数性质

1. log n = Θ(log l (n))，（l为任意常数）；
2. log b(n) = o( n^a )，a>0；
3. a^logbn=n^logba

未完待续，不定期更。