首页 > 编程知识 正文

logn平方与n复杂度,时间复杂度log没有底数

时间:2023-05-03 08:28:20 阅读:167626 作者:1729

算法中log级别的时间复杂度,由于使用了分治的思路,所以该基数直接决定于分治的复杂度。

采用二分法,以2为底,三分法以3为底,其他也是如此。

但是,不管底数是什么,log水平的渐进意义是一样的。

也就是说,该算法时间复杂度的增加与处理数据的少许增加之间的关系相同。

首先考虑o(logx ) n )和o ) logy ) n )、x吧!=y,我们考虑的是n变得无限的情况。

求出n无限大时的logx(n )/logy(n ) n )的极限,可知极限等于lny/lnx,即常数。

也就是说,当n无限大时,这两个东西只有一个常数不同。

所以从研究算法的角度来看log的底数并不重要。

最后,结合上面,我也谈谈大o的定义(算法导论第28页的定义)。

注意将该定义与高等数学中的极限部分进行比较,

这里的定义明显体现了极限的思想,

使n0成为非常大的数字,

很明显,当n大于n0时,可以看出任意底的对数函数实际上相差常数倍。

所以,o(logn )就像o ) n^2)一样,在书中写道,现在可以表达所有底的对数了。

虽然没有非常严密的证明,但我觉得这样说很容易理解。 如果对证明感兴趣的话,可以参照高数量且极限地走向无限的证明。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。