log底数怎么算(时间复杂度中的log)

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

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

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

log底数怎么算(时间复杂度中的log)(1)

假设有底数为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 符号。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页