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

大 0 表达式中的 log 疑问。

  •  
  •   wleexi · 2018-11-28 12:33:28 +08:00 · 2302 次点击
    这是一个创建于 2187 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在学习 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 转换过程是怎么样的。

    5 条回复    2020-02-21 13:15:26 +08:00
    xml123
        1
    xml123  
       2018-11-28 12:42:36 +08:00   ❤️ 1
    对数的换底公式
    lance6716
        2
    lance6716  
       2018-11-28 15:30:27 +08:00
    如果你的书也是写的“ log32 ”而不是 3 比 2 小且底那么一点点的话,书就可以扔了
    wleexi
        3
    wleexi  
    OP
       2018-11-28 17:01:01 +08:00
    @lance6716 那是我是书写的格式问题。现在明白了。谢谢
    zjiajun
        4
    zjiajun  
       2019-02-23 10:54:48 +08:00
    @wleexi 正好看到,也不太明白这个是怎么转换的,望解答下,谢谢
    BlackYau
        5
    BlackYau  
       2020-02-21 13:15:26 +08:00
    @zjiajun
    之前自己不懂的时候搜到了这个问题,现在解决了
    https://blackyau.cc/24.html#ologn-onlogn
    https://i.loli.net/2020/02/21/3g5sRDiflBy7rvN.jpg
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1229 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 18:16 · PVG 02:16 · LAX 10:16 · JFK 13:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.