数据结构与算法之时间复杂度与空间复杂度
1.时间复杂度
1.1 概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
1.2 计算
请计算一下func1基本操作执行了多少次？
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); }
Func1 执行的基本操作次数 ：
- N = 10 F(N) = 130
- N = 100 F(N) = 10210
- N = 1000 F(N) = 1002010
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后，Func1的时间复杂度为：O(N^2)
- N = 10 F(N) = 100
- N = 100 F(N) = 10000
- N = 1000 F(N) = 1000000
就是忽略那些对结果影响不大的项，简明的表示执行次数，而且是考虑的是算法最坏的情况。
下边我们来几个例子练练手：
【实例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 ( N ) .
【实例2】
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); }
时间复杂度为O (M+N ).
【实例3】
void func4(int N) { int count = 0; for (int k = 0; k < 100; k++) { count++; } System.out.println(count); }
时间复杂度为O (1 ).
【实例4】
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; } } }
该程序最坏情况下执行次数为n∗(n−1)/2, 时间复杂度为O (N^2 ).
【实例5】
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; }
二分查找的程序，每循环一次，排除的元素就少一半，我们设该程序的执行次数为X，元素个数为n ，当查找剩余元素个数为1个时，程序还需要查找一次,则有下面等式：
n/2^X=1
则X=log 2 n，即时间复杂度为log 2 n。
【实例6】
计算阶乘递归factorial的时间复杂度？
long factorial(int N) { return N < 2 ? N : factorial(N-1) * N; }
递归的时间复杂度=递归的次数*每次递归执行的次数
该程序需要递归的次数为n 次，所以它的时间复杂度为O ( N )
【实例7】
计算斐波那契递归fibonacci的时间复杂度？
int fifibonacci(int N) { return N < 2 ? N : fifibonacci(N-1)+fifibonacci(N-2); }
次数和=1+2^1+ 2^2+ 2^3+…… +2^(n-1)
=2^n-1
时间复杂度为O ( 2^N )
2.空间复杂度
2.1 概念
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
2.2 计算
【实例1】
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】
int[] fifibonacci(int n) { long[] fifibArray = new long[n + 1]; fifibArray[0] = 0; fifibArray[1] = 1; for (int i = 2; i <= n ; i++) { fifibArray[i] = fifibArray[i - 1] + fifibArray [i - 2]; } return fifibArray; }
该程序开辟了长度为n+1的数组变量,所以空间复杂度为O ( N)。
【实例3】
long factorial(int N) { return N < 2 ? N : factorial(N-1)*N; }
每次递归所有的数据都会占据一块空间，递归的空间复杂度就是递归的次数。
该程序的空间复杂度为O（N）。
3.总结
常见的算法时间复杂度有以下几类：
- 常数阶，如O ( 1 )
- 多项式阶，如O(n^2), O(n^3)
- 指数阶，如递归实现斐波拉契数列O(2^n)
- 对数阶，如二分查找O ( l o g 2 n )
大小顺序：
O(1)<O(logN)<O(N)<O(NlogN)<O(NN)<O(2^N)
