风景区网站代码,苏州企业网站建设服务好,网站建设的前端和后端,网页制作教程教程目录 时间复杂度推导大O方法求解时间复杂度的方法普通顺序结构单循环双循环递归Master定理#xff08;主定理#xff09;递归树方法 空间复杂度 一个算法的好坏根据什么来判断呢#xff1f;有两种一种是时间效率#xff0c;一种是空间效率。时间效率也可称为时间复杂度主定理递归树方法 空间复杂度 一个算法的好坏根据什么来判断呢有两种一种是时间效率一种是空间效率。时间效率也可称为时间复杂度空间效率可以称为空间复杂度。时间复杂度衡量的主要是算法的运行速度而空间复杂度主要衡量的是一个算法所需要的额外空间。 时间复杂度 在进行算法分析时语句总的执行次数 T(n) 是关于问题规模 n 的函数进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度也就是算法的时间量度记作T(n)O(f(n))。 它表示随问题规模n 的增大算法执行时间的增长率和 f(n) 的增长率相同称作算法的渐近时间复杂度简称为时间复 杂度。其中f(n) 是问题规模n 的某个函数。 定义很长个人觉得了解即可对于O()这种体现时间复杂度的方法我们称之为大O记法
推导大O方法
用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不是1,则去除与这个项相乘的常数。 得到的结果就是大O 阶 。
求解时间复杂度的方法 时间复杂度有最坏时间复杂度平均时间复杂度也有最好情况的时间复杂度但我们一般讨论的都是最坏时间按复杂度并且如果没有特殊说明我们也默认为算的是最坏时间复杂度。 我们去计算时间复杂度的时候说白了也就是去数语句执行次数最多的算出来的就是时间复杂度不过要满足大O记法。 O100的时间复杂度为O1只有常数存在的时候常数时间复杂度为O(1)
普通顺序结构
这种可以称作求时间复杂度最简单的。 public static void main(String[] args) {System.out.println(你好);}//执行了常数次时间复杂度为O1单循环
我建议大家做这种的时候要多动手而不是光靠脑子想。尤其我们刚开始接触数据结构的时候。 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);
}双循环
这种分为两种一种是内外两层互不影响一种是外层会影响内层。
两层互不影响的时候 我们一般把log₂n简写成logn外层会对内层产生影响的时候 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)
对于上面这些方法核心还是要根据代码能推出正确的式子。TnTn-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的大小关系希望大家能记住因为不知道啥时候就会用到。 1GB1024MB 1MB1024KB 1KB1024字节
我们在计算空间复杂度的时候计算的是变量的个数而不是占用了多少空间。函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
空间复杂度的计算这我就不细说了相信大家都有相关的教材这部分可以参考教材来学习怎么计算
