专栏首页前端真相时间复杂度中的log(n)底数到底是多少?

时间复杂度中的log(n)底数到底是多少?

其实这里的底数对于研究程序运行效率不重要,写代码时要考虑的是数据规模n对程序运行效率的影响,常数部分则忽略,同样的,如果不同时间复杂度的倍数关系为常数,那也可以近似认为两者为同一量级的时间复杂度。

现在来看看为什么底数具体为多少不重要?

读者只需要掌握(依稀记得)中学数学知识就够了。

假设有底数为2和3的两个对数函数,如上图。当X取N(数据规模)时,求所对应的时间复杂度得比值,即对数函数对应的y值,用来衡量对数底数对时间复杂度的影响。

比值为log2 N / log3 N,运用换底公式后得:(lnN/ln2) / (lnN/ln3) = ln3 / ln2,ln为自然对数,显然这三个常数,与变量N无关。

用文字表述:算法时间复杂度为log(n)时,不同底数对应的时间复杂度的倍数关系为常数,不会随着底数的不同而不同,因此可以将不同底数的对数函数所代表的时间复杂度,当作是同一类复杂度处理,即抽象成一类问题。

当然这里的底数2和3可以用a和b替代,a,b大于等于2,属于整数。a,b取值是如何确定的呢?

有点编程经验的都知道,分而治之的概念。排序算法中有一个叫做“归并排序”或者“合并排序”的算法,它用到的就是分而治之的思想,而它的时间复杂度就是N*logN,此算法采用的是二分法,所以可以认为对应的对数函数底数为2,也有可能是三分法,底数为3,以此类推。

但是不可能是分数或者负数。

说明:为了便于说明,本文时间复杂度一概省略 O 符号。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 为什么数组下标是从0开始?

    数组寻址——arr[i] = base_address + i * type_size(1)

    城市中的游牧民族
  • Linux常用命令

    城市中的游牧民族
  • 使用plsql developer连接oracle数据库

    需要在服务器上安装服务端数据库 本机上安装数据库的客户端及plsql 修改oraname.ora

    城市中的游牧民族
  • 利用热点做捆绑式创意,借势营销一直流行的秘密在哪?

    一个月前,我在给青岛一家连锁酒店做品牌咨询的时候,还在反复跟他们市场部的文案策划讲,在当下社会化媒体环境下,请停止无聊的新闻稿发布,也不要当微博、微信像官方网站...

    貟王軍
  • CVE-2018-1133 Moodle 3.4.1 - 远程执行注入漏洞

    exploit-db网站在3.15日挂出了一个Moodle<3.5版本的一个远程代码执行漏洞,如下所示:

    墙角睡大觉
  • python网络编程之socketser

      在进行网络编程前我们先来说说在网络中服务器与客户端是如何交互的,也就是传说中的TCP三次握手。

    py3study
  • 选型宝访谈:移动互联网时代,报销费控系统如何为企业降本增效

    ...

    选型宝
  • INET_ATON()函数在MySQL5.6版本和5.7版本的差异

    问题 ### The error occurred while setting parameters ### SQL: insert into t_gatewa...

    囚兔
  • 6 图助你理解 SQL 优化策略

    玩 SQL 1 - 2 年的朋友,对于 Execution Plan (执行计划)估计不陌生了。但也有特例,3 - 4 年的朋友有时候也不知道如何查看 Exec...

    Lenis
  • 不等宽柱形图

    今天要跟大家分享的图表是不等宽柱形图! ▽▼▽ 基础等柱形图一般只能展示一个维度的数据,但是如果想要在柱形图中同时展示两个维度的数据(柱高一个维度、柱宽另一个维...

    数据小磨坊

扫码关注云+社区

领取腾讯云代金券