【数据结构】时间和空间复杂度-Java

如何衡量算法的好坏

根据时间复杂度和空间复杂度来判断 

比较项目	时间复杂度	空间复杂度
定义	衡量算法执行时间与问题规模之间的关系	衡量算法在运行过程中所占用的额外存储空间与问题规模之间的关系
表达方式	通常用大O符号表示，如O（n）、O(n^2）等	通常用大O符号表示，如O（n）、O（1）等
关注重点	算法执行时间的增长速度	算法所需额外空间的增长速度
影响因素	算法中基本操作的执行次数	算法所需的额外数据结构占用的空间大小
举例	顺序查找的时间复杂度为 O (n)，随着数据规模 n 的增大，查找时间线性增长	使用一个固定大小的变量，空间复杂度为 O (1)；使用一个长度为 n 的数组，空间复杂度为 O (n)

大O的渐进表示法

【实例1】

推导大O阶方法

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

使用大O的渐进表示法后，Func1的时间复杂度为O（N^2）

我们平时所说的时间复杂度和空间复杂度都是在在最坏情况下的时间复杂度

拓展：怎么计算平均时间复杂度

算平均时间复杂度就是把每种情况出现的概率乘以在这种情况下算法花的时间，然后把所有这些结果加起来。

平均时间复杂度计算公式：

常见时间复杂度计算举例

【实例1】知到循环次数的时间复杂度

【实例2】不知循环次数的时间复杂度

【实例3】常数次执行的时间复杂度

【实例4】冒泡排序的时间复杂度

小tips：求复杂度一定要结合算法思想！并不一定两个 for循环嵌套，时间复杂度O(N)=N^2

【实例5】二分查找的时间复杂度

【实例6】阶乘递归的时间复杂度

【实例7】斐波那契的时间复杂度

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，空间复杂度算的是变量的个数，使用大O渐进表示法。

通俗来讲，空间复杂度就是看这个算法在运行过程中额外占用了多少内存空间。

【实例1】冒泡排序的空间复杂度