1. 时间复杂度
时间复杂度是一个函数，它定性描述该算法的运行时间。
我们在软件开发中，时间复杂度就是用来方便开发者估算出程序运行的答题时间。
那么该如何估计程序运行时间呢，通常会估算算法的操作单元数量来代表程序消耗的时间，这里默认CPU的每个单元运行消耗的时间都是相同的。
假设算法的问题规模为n，那么操作单元数量便用函数f(n)来表示，随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为O(f(n))。
1.1 O(n)等表示什么？
我们常说的时间复杂度 O(n),O(n^2),O(logn)等指的是，算法在最坏的情况下运行时间的上界。
简单理解：代表某个算法的耗时与数据增长量之间的关系。其中的n代表输入数据的量，以最坏的情况来计算
有时候也有例外，主要看探讨复杂度的时候，输入的数据用例不同，复杂度也可能是不同的，同时有些复杂度有些默认规则，比如快排时间复杂度为O(nlogn)，但是最坏的情况，时间复杂度为O(n^2)
时间复杂度为O(n)，就代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。
时间复杂度O(n^2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。
时间复杂度O(logn)，当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。
时间复杂度O(nlogn)，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。
时间复杂度O(1)就是最低的时间复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）
计算复杂度的时候，会忽略常数项，比如 O(100n)就是O(n)的复杂度，O(5n^2) 就是O(n^2)的时间复杂度，但是我们可以看的出来，比如当n=10的时候，O(100n)的用时很明显比O(5n^2)的要多，但是一般情况下，我们默认O(n)的效率要高于O(n^2)
大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。
其他的复杂度 还有 指数级增长O(2^n)，立方阶O(n^3)
1.2 复杂表达式的化简
有时候我们去计算时间复杂度的时候发现不是一个简单的O(n) 或者O(n^2)， 而是一个复杂的表达式，这时候如何去描述呢？
例如：
O(2*n^2 + 10*n + 1000)
首先我们去掉常数项
O(n^2 + n)
如果数据规模大的话，n的影响极低，所以可以将n去掉，最终时间复杂度为：
O(n^2)
1.3 总结
在解题的时候，我们往往可以通过分析时间复杂度来确定算法的效率，也就是找出其中的最优解法。所以在面试的时候，面试官往往在你给出一种非最优解后，询问是否还有更优的解法（时间复杂度低的）。所以这里有一个套路，如果一道题你知道几种解法，先给出一个不算太优的，然后等面试官问，然后再给出最优解（顺便做思考状，还可以让面试官给点提示）。
2. 空间复杂度
算法在运行过程中占用内存空间大小的量度，依旧用O(f(n)）表示。
利用程序的空间复杂度，可以对程序运行中需要多少内存有个预先估计。
注意：算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数
2.1 如何计算
public int climb1(int n){
//边界条件
int result = 1;
//前n-2的台阶数
int n1 = 1;
//前n-1的台阶数
int n2 = 1;
for (int i=2;i<=n;i++){
result = n1 + n2;
n1 = n2;
n2 = result;
}
return result;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
以我们之前写过的爬楼梯代码分析，随着n的变化，内存空间并不会随着n的变化而变化，此时我们说上述代码的空间复杂度为O(1)
int array = new int(n);
for (int i = 0; i < n; i++) {
array[i] = i;
}
2
3
4
从上述代码分析可以得出，主要是array数组在占用空间，随着n的增大，内存空间的占用线性增长，所以上述代码的空间复杂度为O(n)
空间复杂度为O(logn) 一般出现在递归上，递归的空间复杂度计算公式：递归深度N*每次递归所要的辅助空间，如果每次递归所需的辅助空间是常数，则递归的空间复杂度是 O(N)。
比如二分法，用递归的时候，递归深度为 log(n), 空间复杂度就为O（logn）