首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
V2EX  ›  问与答

大 0 表达式中的 log 疑问。

  •  
  •   wleexi · 327 天前 · 803 次点击
    这是一个创建于 327 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在学习 geektime 的<数据结构与算法之美>,在解释大 O 的时候有如下的例子:

    i=1;
    
    while (i <= n)  {
    
       i = i * 3;
    
    }
    
    

    对数之间是可以互相转换的,log3n 就等于 log32 * log2n,所以 O(log3n) = O(C * log2n),其中 C=log32 是一个常量。基于我们前面的一个理论:在采用大 O 标记复杂度的时候,可以忽略系数,即 O(Cf(n)) = O(f(n))。所以,O(log2n) 就等于 O(log3n)。因此,在对数阶时间复杂度的表示方法里,我们忽略对数的“底”,统一表示为 O(logn)。

    疑问是 log3n = log32 * log2n 转换过程是怎么样的。

    4 回复  |  直到 2019-02-23 10:54:48 +08:00
        1
    xml123   327 天前   ♥ 1
    对数的换底公式
        2
    lance6716   327 天前
    如果你的书也是写的“ log32 ”而不是 3 比 2 小且底那么一点点的话,书就可以扔了
        3
    wleexi   327 天前
    @lance6716 那是我是书写的格式问题。现在明白了。谢谢
        4
    zjiajun   240 天前
    @wleexi 正好看到,也不太明白这个是怎么转换的,望解答下,谢谢
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4290 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 25ms · UTC 01:45 · PVG 09:45 · LAX 18:45 · JFK 21:45
    ♥ Do have faith in what you're doing.