征服数据结构中的时间和空间复杂度

一个算法的好坏根据什么来判断呢？有两种一种是时间效率，一种是空间效率。时间效率也可称为时间复杂度，空间效率可以称为空间复杂度。时间复杂度衡量的主要是算法的运行速度而空间复杂度主要衡量的是一个算法所需要的额外空间。

时间复杂度

在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。 它表示随问题规模n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的渐近时间复杂度，简称为时间复 杂度。其中f(n) 是问题规模n 的某个函数。

定义很长，个人觉得了解即可，对于O()这种体现时间复杂度的方法，我们称之为大O记法

推导大O方法

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1,则去除与这个项相乘的常数。
   得到的结果就是大O 阶 。

求解时间复杂度的方法

时间复杂度有最坏时间复杂度，平均时间复杂度，也有最好情况的时间复杂度，但我们一般讨论的都是最坏时间按复杂度，并且如果没有特殊说明，我们也默认为算的是最坏时间复杂度。

我们去计算时间复杂度的时候，说白了也就是去数语句执行次数最多的，算出来的就是时间复杂度，不过要满足大O记法。
O（100）的时间复杂度为O（1），只有常数存在的时候，常数时间复杂度为O(1)

普通顺序结构

这种可以称作求时间复杂度最简单的。

    public static void main(String[] args) {System.out.println("你好！");}//执行了常数次，时间复杂度为O（1）

单循环

我建议大家做这种的时候要多动手，而不是光靠脑子想。尤其我们刚开始接触数据结构的时候。

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

这里给大家留一个题，自己动手试试，看是否真懂了呢？

// 计算func4的时间复杂度？
void func4(int N) {
int count = 0;
for (int k = 0; k < n; k++) {
count++;
}
System.out.println(count);
}

双循环

这种分为两种，一种是内外两层互不影响，一种是外层会影响内层。

1. 两层互不影响的时候
   
   我们一般把log₂n简写成logn
2. 外层会对内层产生影响的时候

    public void func2(int n) {int m = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= (2 * i); j++) {m++;}}}

希望大家能掌握这种方法，这样对于多层循环也就不害怕了，道理都一样

递归

前段时间看到一个求递归算法时间复杂度的视频，我觉得很容易让人理解，希望也能帮助到你们。

Master定理（主定理）

* 我们比较下面这两个哪个时间复杂度大就用哪个

一、规则一
如果左半部大，那么我们最后直接取左半部分作为结果

二、规则二
如果上面两个算出结果相等，我们需要取左半部分结果再乘上logn，两个组合起来才为最后结果

三、规则三
当比较两个，如果右边大，我们需要再判断下面图片这个式子

如果计算后均满足这两个条件，最后结果就是右边的那个结果。

递归树方法

我们拿第一个举例。

我们画出了递归树，这种求解复杂度方法是：叶子数 + 层数 * f(n)

对于上面这些方法，核心还是要根据代码能推出正确的式子。T（n）=T（n-1）+ 其余操作的时间复杂度，这个式子含义就是求时间复杂度的时候等于前n-1的时间复杂度加上另外一些其他的操作所需要用到的时间复杂度。

时间复杂度大小排序：O(1)<0(logn)<0(n)<0(nlogn)<0(n²)<0(n³)<0(2”)<0(n!)<O(n”)

空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=0(f(n)), 其 中 ，n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数。空间复杂度的求解也符合大O记法。

穿插个题外话，现在估计还有好多人弄不清KB,GB,MB的大小关系，希望大家能记住，因为不知道啥时候就会用到。
1GB=1024MB 1MB=1024KB 1KB=1024字节

• 我们在计算空间复杂度的时候，计算的是变量的个数而不是占用了多少空间。
• 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

空间复杂度的计算，这我就不细说了，相信大家都有相关的教材，这部分可以参考教材来学习怎么计算