时间复杂度和空间复杂度是衡量算法优劣的标准，效率可以用算法的时间复杂度来描述，而所占用的存储空间可以用算法的空间复杂度来描述。
- 时间复杂度：用于评估执行程序所消耗的时间，可以估算出程序对处理器的使用程度。
- 空间复杂度：用于评估执行程序所占用的内存空间，可以估算出程序对计算机内存的使用程度。
常见的时间复杂度有：O(1)常数型；O(log n)对数型，O(n)线性型，O(nlog n)线性对数型，O(n2)平方型，O(n3)立方型，O(nk)k次方型，O(2n)指数型。
值得留意的是，算法复杂度只是描述算法的增长趋势，并不能说一个算法一定比另外一个算法高效。这要添加上问题规模n的范围，在一定问题规范范围之前某一算法比另外一算法高效，而过了一个阈值之后，情况可能就相反了，通过上图我们可以明显看到这一点。这也就是为什么我们在实践的过程中得出的结论可能上面算法的排序相反的原因。
如何推导时间复杂度
求解算法复杂度一般分以下几个步骤：
- 找出算法中的基本语句：算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体。
- 计算基本语句的执行次数的数量级：只需计算基本语句执行次数的数量级，即只要保证函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，使注意力集中在最重要的一点上：增长率。
- 用大Ο表示算法的时间性能：将基本语句执行次数的数量级放入大Ο记号中。 其中用大O表示法通常有三种规则：
用常数1取代运行时间中的所有加法常数；
- 只保留时间函数中的最高阶项；
- 如果最高阶项存在，则省去最高阶项前面的系数；
- 下面通过具体的实例来说明以上的推断步骤和规则。
时间复杂度实例
常数阶O(1)
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：
int i = 1;
int j = 2;
int k = 1 + 2;
上述代码执行时，单个语句的频度均为1，不会随着问题规模n的变化而变化。因此，算法时间复杂度为常数阶，记作T(n)=O(1)。这里我们需要注意的是，即便上述代码有成千上万行，只要执行算法的时间不会随着问题规模n的增长而增长，那么执行时间只不过是一个比较大的常数而已。此类算法的时间复杂度均为O(1)。
对数阶O(log n)
先来看对应的示例代码:
int i = 1; // ①
while (i <= n) {
i = i * 2; // ②
}
在上述代码中，语句①的频度为1，可以忽略不计。
语句②我们可以看到它是以2的倍数来逼近n，每次都乘以2。如果用公式表示就是122*2…*2 <=n，也就是说2的x次方小于等于n时会执行循环体，记作2^x <= n，于是得出x<=logn。也就是说上述循环在执行logn次之后，便结束了，因此上述代码的时间复杂度为O(log n)。
其实上面代码的时间复杂度公式如果精确的来讲应该是：T(n) = 1 + O(log n)，但我们上面已经讲到对应的原则，“只保留时间函数中的最高阶项”，因此记作O(log n)。
线性阶O(n)
示例代码：
int j = 0; // ①
for (int i = 0; i < n; i++) { // ②
j = i; // ③
j++; // ④
}
上述代码中，语句①的频度为1，②的频度为n，③的频度为n-1，④的频度为n-1，因此整个算法可以用公式T(n)=1+n+(n-1)+(n-1)来表示。进而可以推到T(n)=1+n+(n-1)+(n-1)=3n-1，即O(n)=3n-1，去掉低次幂和系数即O(n)=n，因此T(n)=O(n)。
在上述代码中for循环中的代码会执行n遍，因此它消耗的时间是随着n的变化而成线性变化的，因此这类算法都可以用O(n)来表示时间复杂度。
线性对数阶O(nlogN)
示例代码：
for (int m = 1; m < n; m++) {
int i = 1; // ①
while (i <= n) {
i = i * 2; // ②
}
}
线性对数阶要对照对数阶 O(log n)来进行理解。上述代码中for循环内部的代码便是上面讲到对数阶，只不过在对数阶的外面套了一个n次的循环，当然，它的时间复杂度就是n*O(log n)了，于是记作O(nlog n)。
平方阶O(n²)
示例代码:
int k = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
k++;
}
}
平方阶可对照线性阶来进行理解，我们知道线性阶是一层for循环，记作O(n)，此时等于又嵌套了一层for循环，那么便是n * O(n)，也就是O(n * n)，即O(n^2)。
如果将外层循环中的n改为m，即：
int k = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
k++;
}
}
那么，对应的时间复杂度便为：O(m * n)。
同理，立方阶O(n³)、K次方阶O(n^k)，只不过是嵌套了3层循环、k层循环而已。
空间复杂度
最后，我们再了解一下空间复杂度。空间复杂度主要指执行算法所需内存的大小，用于对程序运行过程中所需要的临时存储空间的度量，这里的空间复杂度同样是预估的。
程序执行除了需要存储空间、指令、常数、变量和输入数据外，还包括对数据进行操作的工作单元和存储计算所需信息的辅助空间。存储空间通常包括：指令空间（即代码空间）、数据空间（常量、简单变量）等所占的固定部分和动态分配、递归栈所需的可变空间。其中可变空间与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模，S(n)表示空间复杂度。
空间复杂度实例
空间复杂度 O(1)
空间复杂度为O(1)的情况的示例代码与时间复杂度为O(1)的实例代码一致：
int i = 1;
int j = 2;
int k = 1 + 2;
上述代码中临时空间并不会随着n的变化而变化，因此空间复杂度为O(1)。总结一下就是：如果算法执行所需要的临时空间不随着某个变量n的大小而变化，此算法空间复杂度为一个常量，可表示为 O(1)，即 S(n) = O(1)。
空间复杂度 O(n)
示例代码：
int j = 0;
int[] m = new int[n];
for (int i = 1; i <= n; ++i) {
j = i;
j++;
}
上述代码中，只有创建int数组分配空间时与n的大小有关，而for循环内没有再分配新的空间，因此，对应的空间复杂度为S(n) = O(n)。
总结：
本篇文章给大家讲了可以通过时间复杂度和空间复杂度来衡量算法的优劣，同时用具体的实例来讲解如何计算不同方法的时间复杂度和空间复杂度。
参考：