复杂度分析
目前分析算法主要从「时间」和「空间」两个维度来进行分析。时间维度顾名思义就是算法需要消耗的时间，「时间复杂度」是常用的分析单位。空间维度代表算法需要占用的内存空间，我们通常用「空间复杂度」来分析。
所以，分析算法的效率主要从「时间复杂度」和「空间复杂度」来分析。很多时候我们两者不可兼得，有时候要用时间换空间，或者空间换时间。下面我们一起来分别了解「时间复杂度」和「空间复杂度」的计算方式。
时间复杂度
时间复杂度是指执行这个算法所需要的计算工作量，其复杂度反映了程序执行时间「随输入规模增长而增长的量级」，在很大程度上能很好地反映出算法的优劣与否。一个算法花费的时间与算法中语句的「执行次数成正比」，执行次数越多，花费的时间就越多。一个算法中的执行次数称为语句频度或时间频度，记为T(n)，其中n称为问题的规模，当n不断变化时，它所呈现出来的规律，我们称之为时间复杂度。
大O表示法
大O符号是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。算法的复杂度通常用大O符号表述，定义为T(n) = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。
所以我们需要一种复杂度计算方式，不受计算机性能和程序数据的影响，「大O符号表示法」(BigO)就是这种计算方式，既 T(n) = O(f(n))，它表示一个算法的渐进时间复杂度。其中 f(n) 表示代码执行次数之和，O表示正比例关系。
时间复杂度量级
- 常数阶O(1)
- 对数阶O(logN)
- 线性阶O(n)
- 线性对数阶O(nlogN)
- 平方阶O(n²)
- 立方阶O(n³)
- K次方阶O(n^k)
- 指数阶(2^n)
- 阶乘O(n!)
常数阶O(1)
只要没有循环或递归等复杂逻辑，无论代码执行多少行，代码复杂度都为O(1)，上述代码在执行的时候，所消耗的时间不会随着特定变量的增长而增长，即使有几万行这样的代码，我们都可以用O(1)来表示它的时间复杂度
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
线性阶O(n)
for (int i = 1; i <= n; i++) {
j++;
}
在这段代码中，for循环会执行n遍，因此计算消耗的时间是随着n的变化而变化，因此这类代码都可以用O(n)来表示其时间复杂度。
对数阶O(logN)
int i = 1;
while(i<n)
{
i = i * 2;
}
从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)
线性对数阶O(nlogN)
线性对数阶O(nlogN)很好理解，也就是将复杂度为O(logN)的代码循环n遍：
for(int i = 0; i <= n: i++) {
int x = 1;
while(x < n) {
x = x * 2;
}
}
因为每次循环的复杂度为O(logN)，所以n * logN = O(nlogN)
平方阶O(n²)
平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
x++;
}
}
O(n²)的本质就是n * n，如果我们将内层的循环次数改为m：
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
x++;
}
}
复杂度就变为 n * m = O(n * m)。
一些更高的阶级比如O(n³)或者O(n^k)，我们可以参考O(n²)来理解即可，O(n³)相当于三层循环，以此类推。
指数阶(2^n)
数阶时间复杂度（O(2^n)）是一种非常高的时间复杂度，表示算法的执行时间会随着输入规模的增加而指数级增长。这种复杂度通常出现在解决组合问题或者涉及到递归的算法中。
具有指数阶时间复杂度的算法通常需要对所有可能的情况进行穷举，因此执行时间会迅速增加。对于稍微大一点的输入规模，这种算法可能会变得非常慢，甚至无法在合理的时间内完成计算。
举个例子，一个经典的指数阶算法是求解斐波那契数列的递归实现：
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
在这个算法中，每个斐波那契数都是前两个斐波那契数的和。但是，每次计算一个斐波那契数时，都需要递归调用该函数两次。因此，该算法的时间复杂度是指数阶的。
指数阶时间复杂度的算法通常是不可行的，因为其执行时间增长得非常快。在实际应用中，我们通常需要寻找更有效的算法来解决问题，避免使用指数阶算法。
阶乘O(n!)
阶乘时间复杂度（O(n!)）是一种非常高的时间复杂度，表示算法的执行时间会随着输入规模的增加而阶乘级增长。这种复杂度通常出现在需要生成排列或组合的算法中。
阶乘时间复杂度的算法需要考虑所有可能的排列或组合情况，因此执行时间会迅速增加。对于稍微大一点的输入规模，这种算法的执行时间会变得非常慢，甚至无法在合理的时间内完成计算。
以下是一个简单的例子，使用递归方式计算一个整数的阶乘：
public class Factorial {
public static long factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
public static void main(String[] args) {
int number = 5;
long result = factorial(number);
System.out.println("Factorial of " + number + ": " + result);
}
}
在这个例子中，factorial方法使用递归来计算一个整数的阶乘。递归函数将问题分解为规模更小的子问题，然后通过递归调用自身来解决子问题。
然而，这个算法的时间复杂度是阶乘级的，因为对于每个n，都需要递归调用n次来计算n的阶乘。因此，该算法的时间复杂度为O(n!)。
需要注意的是，阶乘时间复杂度的算法通常是非常低效的。对于稍大的输入规模，执行时间会呈指数级增长。因此，在实际应用中，我们通常需要寻找更有效的算法来解决问题，避免使用阶乘时间复杂度的算法。
空间复杂度
既然「时间复杂度」不是计算程序具体消耗的时间，「空间复杂度」也不是用来计算程序具体占用的空间。随着问题量级的变大，程序需要分配的内存空间也可能会变得更多，而「空间复杂度」反映的则是内存空间增长的趋势。
常用的空间复杂度
比较常用的空间复杂度有：O(1)、O(n)、O(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)。
空间复杂度 O(n²)
空间复杂度（Space Complexity）为O(n²)表示算法在执行过程中所需的额外空间与输入规模的平方成正比。这种复杂度通常出现在需要使用二维数组或矩阵的算法中。
public class Matrix {
public static void printMatrix(int[][] matrix) {
int rows = matrix.length;
int columns = matrix[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
printMatrix(matrix);
}
}
在这个例子中，printMatrix方法接收一个二维数组作为参数，并打印该矩阵的元素。为了访问矩阵中的每个元素，我们使用了两个嵌套的循环来遍历行和列。
该算法的空间复杂度为O(n²)，因为在存储矩阵时，我们需要使用二维数组来表示每个元素的位置。矩阵的大小为n×n，因此需要O(n²)的额外空间。
需要注意的是，空间复杂度的O(n²)并不一定代表使用二维数组。它可以是其他数据结构或算法中的计算开销，只要与输入规模的平方成正比即可。
在实际应用中，当算法的空间复杂度为O(n²)时，需要仔细考虑算法的可行性和效率，特别是当n较大时。尽可能寻找更节省空间的解决方案是提高算法效率的关键。
ICP证：