Java架构师-数据机构与算法实战（第一篇）

数学知识回顾

指数

指数函数是重要的基本初等函数之一。一般地，y=a^x函数(a为常数且以a>0，a≠1)叫做指数函数，函数的定义域是 R 。注意，在指数函数的定义表达式中，在a^x前的系数必须是数1，自变量x必须在指数的位置上，且不能是x的其他表达式，否则，就不是指数函数。
在这里插入图片描述

对数

对数函数（Logarithmic Function）是以幂（真数）为自变量，指数为因变量，底数为常量的函数。
对数函数是6类基本初等函数之一。其中对数的定义：
如果ax =N（a>0，且a≠1），那么数x叫做以a为底N的对数，记作x=logaN，读作以a为底N的对数，其中a叫做对数的底数，N叫做真数。
一般地，函数y=logaX（a>0，且a≠1）叫做对数函数，也就是说以幂（真数）为自变量，指数为因变量，底数为常量的函数，叫对数函数。
其中x是自变量，函数的定义域是（0，+∞），即x>0。它实际上就是指数函数的反函数，可表示为x=ay。因此指数函数里对于a的规定，同样适用于对数函数。
“log”是拉丁文logarithm（对数）的缩写，读作：[英][lɔɡ][美][lɔɡ, lɑɡ]。
在这里插入图片描述

级数

级数是指将数列的项依次用加号连接起来的函数。典型的级数有正项级数、交错级数、幂级数、傅里叶级数等。
级数理论是分析学的一个分支；它与另一个分支微积分学一起作为基础知识和工具出现在其余各分支中。二者共同以极限为基本工具，分别从离散与连续两个方面，结合起来研究分析学的对象，即变量之间的依赖关系──函数。

模运算

“模”是“Mod”的音译，模运算多应用于程序编写中。 Mod的含义为求余。模运算在数论和程序设计中都有着广泛的应用，从奇偶数的判别到素数的判别，从模幂运算到最大公约数的求法，从孙子问题到凯撒密码问题，无不充斥着模运算的身影。虽然很多数论教材上对模运算都有一定的介绍，但多数都是以纯理论为主，对于模运算在程序设计中的应用涉及不多。

复杂度
- 时间复杂度
  在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
- 空间复杂度
  对于一个算法，其 [1]时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。