Java基础、中级、高级、架构面试资料

关于常见算法的时间复杂度 Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)

业余杂谈 herman 2716浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog2,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog2,之前的微信号好友位已满,备注:返现
受密码保护的文章请关注“业余草”公众号,回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领
腾讯云】1核2G5M轻量应用服务器50元首年,高性价比,助您轻松上云

说实话,我是真的不懂算法。但是,我知道一个算法的好坏,通常时间复杂度是一个评价的指标之一。

又到了一年的面试季,有些同学在群里反馈算法问题。关于这类问题,我建议大家多去 LeetCode 刷题,多去看看练习练习。因为我对算法问题真的是不太懂!没有专门研究过!

虽然我不懂算法,但是我知道关于算法的时间复杂度。比如:Ο(1)、Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)、Ο(n3)…Ο(2n)、Ο(n!)等所代表的意思!

我在面试的时候,就发现有人连 O(1) 代表什么意思都搞不清楚!

关于时间复杂度,有一个公式:T (n) = Ο(f (n))。怎么解释这个公式呢?特别麻烦,我目前还没有想到比较简单的介绍方式。所以,我就先不解释它了。

所以,我们就先来看看 O(1) 是什么意思?

O(1)

O(1) 也就是最低时间复杂度。代表的是一个常量值。也就是说耗时,耗空间与输入数据的大小无关。无论输入数据增大多少倍,耗时是不变的。

相关算法举例:哈希算法(不考虑冲突的情况),无论在数据量多么大,都是 O(1)。

O(n)

O(n) 理解起来也很简单,就是算法的时间复杂度随着数据量的增大几倍,耗时也增大几倍。

常见的算法举例:遍历算法。

O(n^2)

就代表数据量增大 n 倍时,耗时增大 n 的平方倍,这是比线性更高的时间复杂度。比如冒泡排序,就是典型的 O(n^2) 的算法,对 n 个数排序,需要扫描 n × n 次。

O(n^2) 也有人用 O(n²) 表示。这两个表示是一样的。

O(logn)

当数据增大 n 倍时,耗时增大 logn 倍(这里的 log 是以 2 为底的,比如,当数据增大 256 倍时,耗时只增大 8 倍,是比线性还要低的时间复杂度)。二分查找就是 O(logn)的算法,每找一次排除一半的可能,256 个数据中查找只要找 8 次就可以找到目标。

O(nlogn)

O(nlogn) 就是 n 乘以 logn,当数据增大 256 倍时,耗时增大 256*8=2048 倍。这个复杂度高于线性低于平方。归并排序就是 O(nlogn) 的时间复杂度。

常见的时间复杂度有:常数阶 O(1),对数阶 O(log2n),线性阶 O(n),线性对数阶 O(nlog2n),平方阶 O(n2),立方阶 O(n3),…,k 次方阶 O(nk),指数阶 O(2n) 等。我就不一一列举说明了。

算法的时间复杂度

从上图中可见,我们应该尽可能选用多项式阶 O(nk) 的算法,而不希望用指数阶的算法。

常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)。

常见的算法时间复杂度举例

上图是常见的算法时间复杂度举例。

其实我不搞算法,记住上面常用的几个时间复杂度,能解释它们的意思就行了。想输入学习算法的,可以在公众号里回复“算法”关键字,获得一套免费的视频教程!

其实生活很美好,想的太多也不行。所以,不会,有差距很正常。关键是你要正视你和别人的差距。

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号:xttblog2。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » 关于常见算法的时间复杂度 Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)