版本记录

前言

将数据结构和算法比作计算机的基石毫不为过，追求程序的高效是每一个软件工程师的梦想。下面就是我对算法方面的基础知识理论与实践的总结。感兴趣的可以看上面几篇。
1. 算法简单学习（一）—— 前言
2. 算法简单学习（二）—— 一个简单的插入排序
3. 算法简单学习（三）—— 分治法与合并排序
4. 算法简单学习（四）—— 冒泡排序
5. 算法简单学习（五）—— 函数的增长

单调性

这个性质我们高中的时候就用过，其实定义可以这么说：y随着x的增大而增大，随x的减小而减小，这种就是单调函数，包括单调递增和单调递减函数。

也可以这么定义，如果m ≤ n，则有函数f(m) ≤ f(n)，这种就是单调递增函数，反过来，如果m ≥ n，则有函数 f(m) ≥ f(n)，这种就是单调递减函数。

下取整（floor）和上取整（ceiling）

对于任意一个实数x，小于或等于x的最大整数表示为⌊x⌋，也可以称为对x进行下取整；大于或等于x的最小整数表示为⌈x⌉，也可以称为对x进行上取整。下面看一下取整有关的几个性质。

• 对于任意实数x，都满足如下等式。

x - 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1

• 对于任意整数n，都满足如下等式。
  ⌈n / 2⌉ + ⌊n / 2⌋ = n

• 对于任意整数a，b均大于0，对于任意实数n ≥ 0，都有如下关系式。
  ⌈⌈n / a⌉ / b⌉ = ⌈n / ab⌉
⌊⌊n / a⌋ / b⌋ = ⌊n / ab⌋
⌈a / b⌉ ≤ (a + (b - 1)) / b
⌊a / b⌋⌉ ≥ (a - (b - 1)) / b

这里还需要说明的是，下取整函数f(x) = ⌊x⌋是单调递增函数，上取整函数亦然。

取模运算

其实就是求余运算，我们在OC中可以发现只有整数之间可以求余，但是在swift中浮点数也可以进行求余运算了。

对于任意整数a和任意正整数n，a mod n的值即a / n的余数。

a mod n = a - ⌊a / n⌋ n

余数相等性

如果a mod n = b mod n ，则可以写作 a Ξ b(mod n)。

多项式

给定一个正整数d，n的d次多项式是具有如下形式的函数p(n)：

多项式

这里常数a₀，a₁，... ，a_d，是多项式的系数且不为0。

• 对于一个d次的渐近多项式p(n)，有p(n) = Θ(n^d)。
• 对任意常数a ≥ 0，函数n^a单调递增，对于 a ≤ 0，函数n^a单调递减。
• 若对于某个常数k有f(n) = O(n^k)，则称函数f(n)有多项式界。

指数式

对于任意实数 a > 0、m、n，有下面的等式。

指数等式

这里需要知道的是：任何底大于1的指数函数比任何多项式函数增长的更快。

对数

对任意a > 0, b > 0, c > 0和n，可以有如下关系式。

对数

这里需要知道的是：任何正的多项式函数都比多项对数函数增长的快。

斐波那契数

这个数的递归定义为：

斐波那栔数

可以证明，该数列是以指数形式增长的。

多重对数函数

我们用记号lg*n来表示多重对数，首先要区分下面的定义。

• lg ⁽ⁱ⁾ n 表示从参数n开始，连续应用对数函数i次。
• lg ⁱ n表示n的对数的i次方。

下面我们定义多重对数函数。

多重对数函数

多重对数函数是一种增长很慢的函数

多重对数函数

由上我们可以看出来，我们很少会碰到一个使lg*n > 5的输入规模n。

后记

未完，待续~~~

秋天