算法复杂度
算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。
时间复杂度是学习算法的基石，因此在学习算法之前，必须要知道如何去计算一段代码的时间复杂度，下面就根阿导一起来看看吧。
如何计算一个程序的时间复杂度
如下面一段代码，如何计算它的时间复杂度呢？

    int a= 10;
    
    int b= 10;
    
    System.out.println(a+b);
    


这个应该是很简单的，一眼就能看出来，其时间复杂度是 O(1)，那接下来稍微来个复杂一点的

    int a = n;
    int b = 0;
    for(int i = 0 ; i < a ; i++){

        b++;

    }



有经验的程序员都知道上面的代码时间复杂度为 O(n)，那么时间复杂度究竟是如何推导出来的呢？下面请允许阿导娓娓道来。
假定每一句执行的时间都是 k,下面我将上述按照执行时间来划分，如下图所示

红色代码代码部分执行时间为 3k，原谅色代码部分执行时间为 (n+1)k，蓝色代码部分执行时间为 2nk。
那么上述代码执行时间可表示为 f(n) = (3n+4)k，明显这就是一个函数式，下面会涉及到一个量级的概念，就是将 n 趋近无穷大，然后得出最终渐进结果即为该段代码的时间复杂度，怎么理解呢，如下表所示：




n
f(n) = (3n+4)k




1
7k


100
304k


10000
30004k


100000000
300000004k


10000000000000000
30000000000000004k


∞
∞


你会发现，当 n 变成无穷大的时候，系数的影响微乎其微，我们只关注函数结果影响最大的项，因此上段代码我们会将其复杂度表示为 O(f(n))~O(n)。
既然引出量级的概念，那么在计算复杂度的时候，存在不同的量级就会舍去低的量级，下面给出数学中量级比较关系，如下图所示

小结
笔至此处，已渐尾声，下面我将计算复杂度的流程整理一遍。


先假定每一句执行代码时间为 k


然后分析代码语句，并得出执行时间的数学表达式


接下来就是简化数学表达式，首先将 k 至为 1


将所有常数替换成 1


只保留高阶项（也就是量级最大的一项）


去掉系数，得出最终结果即为时间复杂度


不知各位看官是否已明了，如有疑问，欢迎留言，如有不当之处，请多多包涵和指教！

目录

时间复杂度

空间复杂度

总结

时间复杂度

什么叫做时间复杂度呢？？

我们来看一个简单的程序

 int n = 10 ;
System.out.println("输出" + n);

 这段伪代码运行了多少次呢！ 1次 ，时间时间复杂度为O(1)：常数复杂度/常数阶。

        for (int i = 0 ;i <n; i++){
            System.out.println("第几次"+i);
        }

这个for循环了多少次呢！ n次，时间复杂度为O(n)：线性时间复杂度。

再看下一个

        for (int i = 0 ;i <n; i++){
            for (int j = 0 ;j < n; j ++) {
                System.out.println("第几次" + i+""+j);
            }
        }

这个循环了多少次呢！n*n次，时间复杂度为O()：平方复杂度。

百度百科对时间复杂度的定义是：在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。

我们再把常见的复杂度列举出来看看。

        int j = 0;
        for (int i = 0 ; i < n ; i++) {
            i = i * 2;
            j++;
            System.out.println("第几次"+j);
        }

这个循环了多少次呢！假设我们把次数设为x，那，解得次数，时间复杂度为O(log(n))：对数。

        for (int i = 0 ; i < Math.pow(2,n); i++) {

            System.out.println("第几次"+i);
        }

 这个循环了多少次呢！次，时间复杂度为O()：指数复杂度。

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

简单的讲就是包括下面几部分。

1.存储算法本身所占用的存储空间。

2.算法的输入输出数据所占用的存储空间。

3.算法在运算过程中临时占用的存储空间这三个方面。

int a[] = new int[n];

这个例子的空间复杂度是多少呢？这个数组开辟的空间是多少呢？ O(n)。

总结

时间复杂度和空间复杂度本就是一个相互博弈的过程，一个多另一个就少，根据适当的问题，找到适当的解，这才是好办法。

下面给一张常见数据结构时间和空间复杂度的图作为结尾把。

Big O notation
O(1) 常数复杂度
O(log n) 对数复杂度
O(n) 线性复杂度
O(n ^2)	平方
O(n ^3)	立方
O(2 ^n)	指数
O(n!) 阶乘

一段代码根据 n 的不同情况会运行多少次。
时间复杂度
写程序时考虑优化程序的时间复杂度。

n 越大，优化效果越明显。
以 1 累加到 n 为例:

1.累加计算：
int sum = 0;
for (int i = 1;i <= n;i++) {
    sum += i;
}

时间复杂度和 n 线性相关，所以为 O(n)。
2.公式计算：
sum = n * (n+1) /2

时间复杂度是常数，该代码块在运行时只会执行一次，所以为 O(1)。
递归条件下的时间复杂度
递归状态的递归树
以斐波那契数列为例:
int fib(int n) {
    if (n <= 2) {
	return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

其时间复杂度为 2^n。
此时间复杂度显然不是最优，递归树的画法和斐波那契问题的优化可以看看这篇文章:

如何让递归的斐波那契数列跑的更快
时间复杂度的通用计算方法：Master Theorem
常见算法时间复杂度：

二分查找 O(log n)
二叉树遍历 O(n)
图的遍历 O(n)
归并排序 O(n log n)
搜索算法：DFS、BFS O(n)

空间复杂度
1.数组的长度

一般数组的最大长度，就是其对应的空间复杂度
2.递归的深度

关于时间复杂度的计算理解
前言
一、循环的 判定条件 没有主体变量的参与
1.1 非递归程序
1.1.1 最基础类型
1.1.2 迷惑类型
1.1.2.1 猜测+验证法
1.1.2.2 级数求和
1.2 递归程序
1.2.1 代入法
1.2.2 主定理法
1.2.3 递归树法
二、循环的 判定条件 有主体变量的参与


前言
如果代码的执行最多总次数可以被表示为一个多项式。

那么时间复杂度就是 

   保留最高次方、且去掉常数。

之后的结果。 所以，求一段代码的时间复杂度，就是 得到关于次数 t 的多项式，再去掉常数和保留最高次方即可。 

然而，求出 t 并不是那么容易的。要懂得如何从代码中提取出 t 的多项式。

主要分为以下两种题型：


一、循环的 判定条件 没有主体变量的参与

此类问题的又可分为两种类型

1.1 非递归程序
1.1.1 最基础类型
for(int i = 0; i < n; ++i)
	for(int j = 0; j < n; ++j)
		for(int k = 0; k < 2; ++k)
			A[i][j] = 100;

for(int i = 0; i < n; ++i)
		cout << "999" << endl;

第一段代码是三层循环嵌套，第二层代码是一层循环。

可以轻易的看出,

 第一段代码最内层的语句最多执行 $2n^2$ 次.

 第二段代码最内层最多执行 n 次

所以此段代码的 最多情况下 的总执行次数为 $2n^2+n$ 次,

若记执行次数为, 则

$t <= 2n^2+n$

根据 “留高次，去常数” 的原则,  $0 < t <= n^2$.

用 “大 O 表示法” 记为

$O(2n^2 + n)$

但是当 $n\to\infty$ 时， 后面的低次项 n 与常系数 2 就显得微不足道了。所以为了更简洁的描述与比较快慢，可记为

$O(n^2)$
1.1.2 迷惑类型

还是刚刚的那段代码,只不过做了些许的改动。就足以让很多同学迷惑

for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= i; ++j)
		for(int k = 0; k < 2; ++k)
			if(A[i][j] > 999)
				A[i][j] = 100;

for(int i = 0; i < n; ++i)
		cout << "999" << endl;

可以看出，此程序执行次数最多可能的语句还是 第一层循环的最内层语句
				A[i][j] = 100;

这样的语句我们称为 主体语句

所以根据 留最高, 去常数。原则，我们只关心主体语句的执行过程，而不用去管第二个循环。此时代码简化为:
for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= i; ++j)
		for(int k = 0; k < 2; ++k)
			if(A[i][j] > 999)
				A[i][j] = 100;

又，第三个循环的作用不过是给执行次数 t 的多项式添上系数 2 而已，所以也可以去掉。
for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= i; ++j)
		if(A[i][j] > 999)
		  A[i][j] = 100;

为什么不去掉 判断语句 呢？？因为我们期望得到主体语句的最高执行次数，所以期待每次 判断语句 都会执行。所以在判断复杂度的时候,所以此时可以忽略判断语句。

即:
for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= i; ++j)
		A[i][j] = 100;

此时有两种方法解决这个问题：
1.1.2.1 猜测+验证法

第一个循环从 0到n-1 共会执行 n 次

而对于第二个循环对的执行次数取决于第一个循环。

但在最多情况下，

也就是 i = n 时，

第二个循环也会执行到 j = n.

此时两个循从 1 到 n 都执行了 n 次. 所以复杂度依然为 $n \cdot n = O(n^2)$
1.1.2.2 级数求和

众所周知，当 i = n 时，j所在的循环会执行n次，其中每一次都会使主体语句执行 1, 2 … n 次。

次数如上表所示,所以总执行次数为



 留最高, 去常数。后，为 $O(n^2)$
1.2 递归程序
1.2.1 代入法
$T(n)=\left\{
\begin{aligned} &
1 & , & n=1, \\
2T(n/2)+n & , & n>1.
\end{aligned}
\right.$

此类问题分四步走:

写 T(n) 的迭代式(一直文本替换迭代下去)。
对每次迭代标号，从1到m。
利用 m 与递归截至条件的关系式 解出 m, 代回迭代式。
留最高，去常数。



1.2.2 主定理法
1.2.3 递归树法
二、循环的 判定条件 有主体变量的参与
例题如下：


 我们可以观察到：主体语句执行多少次 取决于 绿色框的值 是否符合循环的判定条件。
此时，我们是无法得知主体语句的循环次数 t 到底是多少的。

这是由于主体语句的循环与否，是取决于循环条件的。

 如果满足判定条件，则主体语句循环，循环次数增加。

此类题的解题步骤一般分为 4 步：


列出 主体语句的执行次数 与 绿色框值 的表格

以第一个为例：




建立 F(t) 方程

  其中自变量 t 为 主体语句的执行次数，因变量为 绿色框值


将 F(t) 代回循环中的判定条件式，解出 t 变量。

  以第一个为例：


$n  \geqslant (t+1)^2 \\ 
\Rightarrow n \geqslant t^2 + t \\  
\Rightarrow  \sqrt{n} \geqslant t + \sqrt{t}$

4. 留高次，去常数

$t \leq \sqrt{n} \\
时间复杂度为 O(\sqrt{n})$