文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

怎么理解Java算法复杂度

2023-06-02 09:13

关注

本篇内容主要讲解“怎么理解Java算法复杂度”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“怎么理解Java算法复杂度”吧!

大O符号

衡量时间复杂度通常使用”大O符号“。什么是大O符号?我们需要先看看一些数学知识:函数和极限。

2.1、数学举例:

00001. 一元二次函数f(x)=2x^2+2x+2;

00002. 当x趋于无穷大的时候,记作x—>∞。

00003. x->∞,f(x)=2x^2+2x+2 = 2x^2 = 2x^2。

上述第3项,当x无穷大的时候2x^2+2x+2约等于2x^2,在极限思想(算法分析)里面可以理解为2x^2+2x+2=2x^2。原因如下:

当x=5的时候:

2x^2+2x+2=62.

2x^2=50.

当x=500的时候:

2x^2+2x+2=501002

2x^2=250000.

通过上面的例子,继续增大x的值,甚至无穷大的时候,f(x)函数中的2x+2这一项就可以忽略不计了。所以x->∞时,(2x^2+2x+2)约等(2x^2),或者(2x^2+2x+2)=(2x^2)。并且在极限思想里面,2x^2前面的系数2也是可以省略的。也就是说x->∞的时候,2x^2~x^2。

通过极限的思想,我们将函数f(x)=2x^2+2x+2,省略剩余项为x^2。也就是说x->∞时,f(x)=2x^2+2x+2=x^2;使用大O符号表示:x->无穷大,f(x)=O(x^2)。

2.2、概念

大O是用来刻画被截断的无穷级数尤其是渐近级数的剩余项。大O符号表示函数的渐进性上界。就好比上面的数学举例,函数f(x)=2x^2+2x+2 渐进级数的剩余项就是x^2,记作O(x^2)。也就是说O(x^2)是f(x)的渐进性上界。

时间复杂度

题目:求1+2+3+……+n的和。(高斯算法)

● 初级程序员的代码:

… …

    for (int i = 1; i <= n; i++) {

        sum+=i;

    }

… …

分析:

00001. 上述代码中的sum+=1执行多少次? 答案:n次。

00002. int i=1执行1次。

00003. i<=n执行n+1次。(因为for循环执行的顺序,只有i大于n时才会停止循环,所以i=n+1的时候,还会再判断一下i<=n,所以相比较而言会多执行一次)。

00004. i++执行n次。

汇总一下,上述代码执行n+1+n+1+n=3n+2次。

如果用极限思维,n->∞,3n+2 ~ 3n ~ n;记作O(n)。O(n)就是上述代码的时间复杂度。

● 高级程序员的代码:

… …

   (1+n)*n/2

… …

如上,同样的计算1加到n,采用高斯算法就简单多了。上述代码只需要执行1次,没有循环。所以时间复杂度就是O(1)。

● 小结

O(1)和O(n)的区别是什么呢?当上述”初级程序员代码“和”高级程序员代码”中的变量n不断增大的时候,高斯算法的时间复杂度基本不变,还是O(1)。但是“初级程序员代码”的时间复杂度就会增加。

对于计算机来说,高斯算法求解1连续加到n的计算速度远远大于for循环的速度。速度越快,系统的性能就会越好。

到此,相信大家对“怎么理解Java算法复杂度”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯