数据结构---时间复杂度与空间复杂度

---

1. 知识背景

衡量一个算法的好坏是根据算法执行时所用的时间与消耗的内存空间所决定的。衡量时间效率的定量为时间复杂度，衡量空间效率的定量为空间复杂度。

在早期计算机发展阶段，内存技术不够成熟，容量十分小，所以开发人员追求通过牺牲时间效率追求空间效率。

在当前计算机发展阶段，内存容量不断增大，开发人员主要追求时间效率，所以我们现在比较注重时间复杂度。

2. 什么是时间复杂度？

时间复杂度在计算机科学中的定义就是一个描述程序执行次数的函数，它大略地（数据并不精准！）定量地描述了程序执行的时间，实际上因为各种因素的不同（比如硬件设备等），我们是无法计算出执行一段程序所需的时间的，只有上机测试才能够知道。我们不可能对每个算法都实现一遍去测试（成本太高！），所以我们需要找出衡量这些算法优劣（针对运行时间讲）的规则。
这就是时间复杂度的规则：

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

3. 空间复杂度

空间复杂度用于定量地描述一个算法临时占用（并不是一开始就开辟好的内存）的存储空间大小，空间复杂度不是计算程序本身占用了多大的空间（不是计算代码量），而是计算变量的个数，
计算规则与时间复杂度类似，均是大O渐进表示法！

4 .大O渐进表示法：

1. 用常数1表示运行时间函数中的加法常数（比如2n+10,则表示为2n+1）。
2. 修改运行时间函数，修改后，只剩下最高项。
3. 如果最高阶项存在且不是1，去掉与最高阶项相乘的常数.（比如：2n,修改成n)
   最终得到的结果：
   O(修改后的函数)
   比如O(n),O(n^2)等。

对于一些算法的时间复杂度存在最好，最坏，平均的情况：

这种情况比如：在N个元素数组中查询数据，
最好的情况只查询 1 次即可，
最坏的情况是查询到最后：N次。
平均即取最好与最坏的平均值，进行N/2次。

 我们一般考虑的均是算法的最坏情况，在进行算法选择时，比较不同算法的时间复杂度最坏情况，
这样最科学。

5. 常见的时间复杂度举例+总结：

举例1 ：

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);
}

代码分析 ：

总结： 对于具体可数的语句，不需要计算（按照大O渐进法会直接变为1，如果到那时没有最高项，则结果直接为O（1）).

时间复杂度：第一个for语句 2*N，while语句循环次数为常量，不需要计算了
根据大O渐进表示法：此算法的时间复杂度为O（n）。

举例2 ：

// 计算func3的时间复杂度？
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);
}

代码分析：
时间复杂度为：第一个for语句 M + 第二个for语句 N = M+N。
根据大O渐进表示法，结果为O（M+N）。

 总结：时间复杂度的表示可以有两个不同的参数

举例3：

// 计算func4的时间复杂度？
void func4(int N) {int count = 0;for (int k = 0; k < 100; k++) {count++;}System.out.println(count);
}

代码分析：此例中有一个for语句，执行100次，有两条普通语句，执行两次，共100+2=102次
根据大O渐进表示法：常数取1。故时间复杂度为O（1）。

举例4：

// 计算bubbleSort的时间复杂度？
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 == true) {break;}}
}

代码分析：

总结：当看到比较复杂的代码时，直接取找最高阶项即可，其余进行不需要计算。

代码分析：观察两个for语句，随着end值的不断减小，
时间复杂度为：（end-1）+（end-1-1）+…1。这是一个等差数列
计算结果为：

举例5：

// 计算binarySearch的时间复杂度？
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;elsereturn mid;}return -1;
}

代码分析：

总结：求时间复杂度的精髓是从具体算法中抽象出相应的运行时间规律，而不是套公式，具体问题具体分析。

举例6：

// 计算阶乘递归factorial的时间复杂度？
long factorial(int N) {return N < 2 ? N : factorial(N-1) * N;
}

代码分析：时间复杂度是求大体的执行次数，此递归的规则是
递归的次数*递归中语句的执行次数。（因为递归一次后，只生成一个函数，不想斐波那契数列，递归多个函数）。

可以看出此函数的算法复杂度为O(n).

举例7：

// 计算斐波那契递归fibonacci的时间复杂度？
int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

代码分析：斐波那契数列并不是一般的递归，其递归一次会产生多个递归函数。所以不能够直接套用一般递归求时间复杂度的规则！

从具体的实现中分析如图：

此时计算斐波那契数列的时间复杂度就可以用
递归函数的个数*执行语句的规则来计算了

最终结果为：O（2^n）。

总结：对于树的递归建议画图来表示计算。

6. 空间复杂度的举例与总结：

前面已经讲过，空间复杂度是指算法格外占用的（即临时开辟的空间）的变量计算。

举例1：

// 计算bubbleSort的空间复杂度？
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 == true) {break;}

代码分析：此排序算法并没有临时开辟内存，所以空间复杂度为：
O（1）。

举例 2：

// 计算fibonacci的空间复杂度？
int[] 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个空间，所以空间复杂度为O(N)。

举例三：

// 计算阶乘递归Factorial的空间复杂度？
long factorial(int N) {return N < 2 ? N : factorial(N-1)*N;
}

代码分析：对于函数递归时，每递归一次，都会给函数开辟一块内存

所以此递归的空间复杂度为O（n）。

总结：

我们以后常遇到的复杂度：
O(1)<O(log2N)<O(N)<O(N*log2N)<O(N^2).