不认同老师说复杂度分析里的常数系数是没有意义的

不认同老师说复杂度分析里的常数系数是没有意义的

在同数量级的复杂度算法之间的比较,系数还是有一定意义的。

正在回答 回答被采纳积分+1

登陆购买课程后可参与讨论,去登陆

1回答
liuyubobobo 2021-07-18 17:29:55

常数项是有意义的。我在哪里说常数项没有意义了,给我一个位置,我听一下。


但是:


1)在大 O 符号下,常数项被忽略了。所以在大 O 意义下,不考率常数项;(我怀疑我表述的就是在大 O 符号下,常数项没有意义。这是这个符号的定义。)


2)算法优化首先要看的是复杂度级别的优化,而不是常数项的优化。从 O(n^2) 到 O(nlogn) 的改进是巨大的。这一点我们在课程中会有具体是的实验,让大家直观地体会到这一点。


3)在个别情况下,会出现高级别复杂度反而比低级别复杂度快的情况,比如 O(n^2) 反而快于 O(nlogn) 或者 O(nlogn) 快于 O(n)。这些在课程中会针对专门的算法有介绍,也会有具体的实验,让大家看到这一点。


继续加油!:)

  • 提问者 洛奇2019 #1

    时间复杂度反映的是数据规模 n 很大的时候的一个增长趋势,所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中,我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据,所以,在对同一阶时间复杂度的排序算法性能对比的时候,我们就要把系数、常数、低阶也考虑进来。

    视频时间点我下班回去找一下。

    2021-07-19 18:40:43
  • liuyubobobo 回复 提问者 洛奇2019 #2

    是的。实际上,比如对于小数据量,使用插入排序可以优化,这一点我在课程中会专门强调的。

    2021-07-20 07:24:00
  • 提问者 洛奇2019 回复 liuyubobobo #3

    不单单是小数据量,在同一级别时间复杂度下有多种算法时,如果希望把性能优化做到极致,系数和低阶就需要考虑了。

    2021-07-20 19:34:44
问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2583    人
  • 解答问题       1082    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师