找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-CSDN博客
所属专栏：数据结构（Java版）
目录
时间复杂度
概念
大O的渐进表示法
相关练习
例1：
例2：
例3：
例4：
例5：
例6：
例7：
例8：
空间复杂度
概念：
相关练习：
例1：
例2：
例3：
接下来，将开始数据结构的学习了。
我们如果衡量一个算法的好坏呢？这个算法到底怎么样呢？
有的小伙伴可能会说：直接把这个代码拷贝到编译器中，看看运行时间是多少，不就行了嘛。的确这个方法在同样的情况下确实可以。比如说：同样是计算斐波那契数列的第 n 项。下面有两份代码，我们就可以把它们分别给到编译器，让其运行看时间是多少？
public class Test {
public static int fib(int n) {
// 递归求
if (n < 2) {
return 1;
}
return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(fib(n));
}
}
public class Test {
public static int fib(int n) {
// 迭代求
int c = 0;
int a = 1;
int b = 1;
if (n < 2) {
return b;
}
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(fib(n));
}
}
由上可见：用迭代求斐波那契数列的第 n 项比用递归求效率更高，也就是说迭代的算法思想在这里的应用更好。
但是如果每一个代码都用编译器去跑，那就有点浪费时间了，并且还不一定准确。因为电脑的处理器不一样，效率肯定也是不一样的。因此，就提出了用时间复杂度的概念和空间复杂度的概念来重新作为这个标准。 下面就来介绍这两个概念。
时间复杂度
概念
什么是时间复杂度？时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
大O的渐进表示法
概念我们已经知道了，那么接下来就该了解，时间复杂度的计算了。时间复杂度就是通过代码的执行次数来确定的。实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
当推导出了代码的执行次数之后，就需要用到下面的规则，来简化得到最终的表达式。
规则：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果 最高阶项的系数 不是1，则把这个系数变成1。得到的结果就是大O阶。
相关练习
求下列代码的时间复杂度。
例1：
void func1(int N) {
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
count++;
}
}
for (int k = 0; k < 2 * N; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}
System.out.println(count);
}
所以最终的执行次数是： N^2 + 2N + 10 。这个结果肯定是符合上面的化简规则的。
首先，根据规则1，把10变成了1，N^2 + 2N + 1 ；
其次，根据规则2，只保留最高阶项，N^2 ；
最后，去掉最高阶项的系数。因为这里的最高阶项的系数是1，因此就不变：O(N) 。
这里也可以证明一下这个规则：
因为这个N的取值是不固定的，如果这个N的取值是100的话，那么这个10对最终结果的影响不是很大。因此可以用1来代替。既然N的取值可以是100，那也就是10000，甚至更大。我们在数学中学过随着X的增大，X^2 与 2X的差值同样是越来越大。因此 2X 也是可以舍去的。因此最终就只剩下了最高阶项，同样其系数对齐的影响同样不大。
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况： 最坏情况：任意输入规模的最大运行次数(上界) ；平均情况：任意输入规模的期望运行次数 ；最好情况：任意输入规模的最小运行次数(下界) 。
例如：在一个长度为N数组中搜索一个数据 x 最好情况：1次找到 ；最坏情况：N次找到。平均情况：N/2次找到。
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。
例2：
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}
System.out.println(count);
}
例3：
void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
count++;
}
for (int k = 0; k < N ; k++) {
count++;
}
System.out.println(count);
}
注意：时间复杂度计算的是执行次数最多的，但是这里的M和N并未表明具体值，因此都不能省略。
例4：
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
System.out.println(count);
}
注意：这里的 N 其实就是用来迷惑我们的。
例5：
void Swap(int[] array, int i , int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false;
}
}
// 如果 sorted 为true，就说明这组数据已经是有序的了
if (sorted) {
break;
}
}
}
变型：刚刚我们求的是最坏的情况，现在我们来求最好的情况。
首先，得想一下什么时候冒泡排序的情况最好，既然前面，我们在算最坏的情况是是每一个都要执行，也就是说数组中元素的顺序是刚好和我们要排的序是相反的，因此每一项都得重新排序。那么最好的情况也就可以分析的出来了，就是当这个数组中元素的顺序刚好和我们要排的序是相同的，也就是说这个数组已经是有序的了。怎么知道有序呢？就是通过这个 sorted 来判断的，如果是true，就说明已经有序；否则，就是无序。要知道有序，肯定得把这个数组遍历一遍才行。那么执行的次数就是N次，时间复杂度就是：O(N) = N 。
例6：
int binarySearch(int[] array, int value) {
int begin = 0;
int end = array.length - 1;
while (begin <= end) {
int mid = begin + ((end-begin) / 2);
if (array[mid] < value)
begin = mid + 1;
else if (array[mid] > value)
end = mid - 1;
else
return mid;
}
return -1;
}
上面是一个二分查找的代码，和我们前面的代码有点不一样。这个是 while循环，没有明确表明循环内部代码的执行次数，而 for循环明确表明了会执行多少次。同样计算时间复杂度是按照最坏的情况来分析的，二分查找，什么情况最坏呢？ 就是当我们找到了只剩下最后一个元素的时候，这个时候已经没有其他元素了，只有这个元素了或者找不到。只要比较一下，就可以了。
至于为什么在元素个数为1时就可以停止查找，这是因为二分查找的核心思想是通过不断缩小查找区间来定位目标值。当区间缩小到只包含一个元素时，这个元素要么就是我们要找的目标，要么就说明目标不存在于数组中（如果是在查找过程中没有提前终止的话）。在这种情况下，我们不需要也不应该再继续“分半”查找，因为没有更小的区间可以探索了，直接判断这最后一个元素是否为目标即可。因此当只剩下一个元素的时候，不需要再查找了，只需要比较就行了。而比较是在查找的代码次数中，因此不需要再+1了。
数组元素个数为 N
设查找的次数为 X 时，此时元素个数为 1，
那么可得出：N / 2 ^ X = 1
⇒ N= 2^X
log2 N=log2 2^X = X
X = log2 N
因此查找的次数就是x，那么对应的时间复杂度也就是：O(log2 N)（已是最简：无常数项、只有一项，无需化简）。
注意：这里的log2 N，是表示以2为底，N的对数。但是有时候会把这个简写成lg N ，我们也知道这个是以10为底，N的对数，这个也算是对的，注意一下就行了。
例7：
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}递归的时间复杂度 = 递归的次数 * 递归中的代码执行的次数。
因为递归其实也算是另一种意义上的迭代（循环），递归的次数就是外层循环的次数，每一次递归的之后执行的次数就是内层循环执行的次数。
递归执行了N-1次，根据规则化简：常数去掉。因此递归的时间复杂度是：O(N)
注意：这里可能有小伙伴会疑惑：递归的过程中递是1次，归也是一次，不应该递归的次数 X 2吗？ 不不不，递归在递的时候，那并没有执行完1次，执行到一半的时候就递下去了，只有归的时候这1次才算执行完毕了。
例8：
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}
再经过规则化简（去掉常数），最终的时间复杂度就是O(2^N) 。
上面就是一系列有关时间复杂度的练习。下面我们再来学习空间复杂度。
空间复杂度
概念：
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少字节的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
同样直接通过练习来感受一下吧。
相关练习：
例1：
public void Swap(int[] array, int i , int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false;
}
}
if (sorted) {
break;
}
}
}计算空间复杂度就算看这个代码为了做这件事，创建了多少个临时变量。
end、sorted、i、Swap中的i、j 、tmp这些都是的，总共是6个。因为采用的是大O渐进表示法，所以常数化为1，最终的空间复杂度就是O(1)。
注意：
1. 可能有小伙伴会说这个数组为什么不算呢？因为这个数组是存储在堆区的，而我们只是创建了一个形参引用（不过这个形参得考虑进去，但因为是粗略估计，所以可以不算）来指向这个数组而已。并没有真正地在堆区用一块空间来创建数组。
2. 这个end 和 i 并不是说创建了100次，就占用了100分临时空间来存储它，永远只有一份空间，只不过这个空间中的值会发生变化而已。
例2：
long[] fibonacci(int N) {
long[] fibArray = new long[N + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= N ; i++) {
fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
}
return fibArray;
}上述代码是为了计算第n个斐波那契数。但是却创建了一个数组。因此空间中的临时变量个数是N+1、i 。根据规则（去掉常数）：O(N)。
例3：
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}上述代码是通过递归来计算第N个斐波那契数。每一次递归都会创建一份新的临时空间，递归N次，会创建N-1分临时空间，再加上原本的空间，就是N分空间，因此最终的结果就是O(N)。
上面就是时间复杂度和空间复杂度的全部内容啦！
好啦！本期 初始Java篇（JavaSE基础语法）（8）认识String类（下）的学习之旅就到此结束了！ 我们下一期再一起学习吧！
