判断一个算法的优劣需要从时间维度和空间维度来估量
时间维度：是指执行当前算法所消耗的时间，我们通常用时间复杂度来描述。
空间维度：是指执行当前算法需要占用多少内存空间，我们通常用空间复杂度来描述

一、时间复杂度（Time Complexity）

一个算法执行所耗费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 $T(n)$ 。

时间频度T(n)中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。
变化时呈现什么规律，引入时间复杂度的概念。算法的时间复杂度也就是算法的时间度量，记作： $T(n) = O(f(n))$ 。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。

这种表示方法我们称为大O符号表示法，又称为渐进符号，是用于描述函数渐进行为的数学符号
注意：这里表示的是近似，是函数关系，代码的执行次数T(n) ≠ f(n)
例：冒牌排序的执行次数函数 $T(n) = n (n-1) / 2$ ，而其时间复杂度是 $T(n) = O(n²)，f(n) = n²$ 是T(n)的同数量级函数，当n趋近于无穷大时候， $T(n) ≈ 0.5n²$ ，n²这个时间复杂度函数是说算法的运行次数会接近随n呈常数C×n的平方形式变化这里只是接近而不是准确。即执行次数保留最高阶项。

常见的时间复杂度量级有：
常数阶： $O(1)$
对数阶： $O(logn)$
线性阶： $O(n)$
线性对数阶： $O(nlogn)$
平方阶： $O(n^2)$
立方阶： $O(n^3)$
指数阶： $O(2^n)$

从上至下依次的时间复杂度越来越大，执行的效率越来越低。

常数阶 $O(1)$

$O(1)$ ，表示该算法的执行时间总是为一个常量，不论输入的数据集是大是小，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

int i = 1;
int j = 2;
int k = i + j;

上述代码执行时间不会随着变量n的增加而增长，不管这种代码有多少行，其时间复杂度都是 $O(1)$

线性阶 $O(n)$

$O(n)$ ，表示一个算法的性能会随着输入数据的大小变化而线性变化，如

for (int i = 0; i < n; i++) {
     sum += i;
}

for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码的时间复杂度是 $O(n)$ 。

平方阶 $O(n^2)$

$O(n^2)$ ，表示一个算法的性能将会随着输入数据的增长而呈现出二次方增长。最常见的就是对输入数据进行嵌套循环。如果嵌套层级不断深入的话，算法的性能将会变为立方阶 $O(n^3)$ ， $O(n^4)$ ， $O(n^k)$ 以此类推

int sum = 0;
for(i = 1; i <= n; i++){
   for(j =1; j <= n; j++){
       sum += i * j;
    }
}

指数阶 $O(2^n)$

$O(2^n)$ ，表示一个算法的性能会随着输入数据的每次增加而增大两倍，典型的方法就是裴波那契数列的递归计算实现

int Fibonacci (int number) {
    if (number <= 1) return number;
    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

对数阶 $O(logn)$

int i = 1;
while (i < n) {
    i = i * 2;
}

在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了，直到i不小于n退出。我们试着求解一下，假设循环次数为k，则 $2^k=n$ ==> $k=log₂n$ 。因此这个代码的时间复杂度为 $O(log₂n)$
如果代码是 i = i * 3 则时间复杂度为 $O(log_3n)$ ， $O(log_2n)$ 和 $O(log_3n)$ 可以通过换底公式换成以2为底的对数，也就是 $log_3n=log_2n \cdot log_32$ ，且可以忽略系数 $log_32$ ，所以都记做 $O(logn)$ 。 $logn$ 计算机默认是2为底的;
换底公式参考：https://www.jianshu.com/p/663a9992fb00

线性对数阶 $O(nlogn)$

$O(nlogn)$ ，就是将时间复杂度为对数阶 $O(logn)$ 的代码循环n遍的话，那么它的时间复杂度就是 $n * O(logN)$ ，也就是了 $O(nlogn)$ ，如下：

for(i = 1; i < n; i++) {
    int j = 1;
    while (j < n) {
        j = j * 2;
    }
}

二、空间复杂度（Space Complexity）

是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，一个算法所需的存储空间用 $f(n)$ 表示。 $S(n)=O(f(n))$ ，其中n为问题的规模， $S(n)$ 表示空间复杂度

空间复杂度比较常用的有：O(1)、O(n)、O(n²)

空间复杂度 $O(1)$

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 $O(1)$

int i = 1;
int j = 2;
++i;
j++;
int k = i + j;

代码中的 i、j、k 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 $S(n) = O(1)$

空间复杂度 $O(n)$

int[] m = new int[n]
for (i = 1; i <= n; ++i) {
   j = i;
   j++;
}

第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 $S(n) = O(n)$

void fun (int n) {
    int arr[10];
    if (n < 0) {
        return 1;
    } else {
        return fun(n - 1);
    }
}

每次调用fun函数就会创建一个10个元素的整型数组，调用次数为n，空间复杂度： $O(n*10)=O(n)$

注意：

递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。递归是要返回上一层的，所以它所需要的空间不是一直累加起来的，如：裴波那契算法的空间复杂度 $S(n) = O(n)$

图来源：https://www.bigocheatsheet.com/

image.png

时间/空间复杂度