江苏龙网

  1. 首页 > 生活 > >

有谁知道这些程序的时间复杂度咋求 （求O(?)）

推了好久的说，如果有错误请指正。。。左上：log*(n)右上：T(n) = T(n/2) + T(n/4) + O(1) =\u0026gt; n ^ 0.6942左下：O(n)G(n, m) = n * mF(n) = G(2, F(n-1)) = 2F(n-1) = 2^nTG(n, m) = TG(n, m-1) + O(1) =\u0026gt; TG(n, m) = O(m)TF(n) = TF(n-1) + TG(2, F(n-1)) + O(1) = TF(n-1) + TG(2, 2^(n-1)) + O(1) = TF(n-1) + 2^(n-1) =\u0026gt; TF(n) = 2^n但是，考虑int只有32位，当n很大(\u0026gt; 32)时，F(n) = 0, 所以TF(n) = TF(n-1) + TG(2, F(n-1)) + O(1) = TF(n-1) + TG(2, 0) + O(1) =\u0026gt; TF(n) = O(n)右下： O(1), 常数的scale为2147483647G(n) = G(n-1) + 2*n - 1 = n^2TG(n) = TG(n-1) + O(1) = O(n)TF(n) = TG(n-1) + TG(G(n-1)) = O(n-1) + TG((n-1)^2) = O(n-1) + O((n-1)^2) = O(n^2)但是，考虑到int只有32位，当n很大(\u0026gt;46340)时，TF(n) = TG(n-1) + TG(G(n-1)) = O(n-1) + TG( O(2147483647) ) = O(2147483647) = O(1)
■网友
有谁知道这些程序的时间复杂度咋求 （求O(?)）

好，这道题完美的解决了。
■网友
为什么这个题这么像贵系邓俊辉数据结构课的期中考试题的风格？求折叠
■网友
都写n^100肯定没错...这种乱用大O标记的老师都可以回去重读...
■网友
【有谁知道这些程序的时间复杂度咋求 （求O(?)）】 有谁知道这些程序的时间复杂度咋求 （求O(?)）
乱用O的该死一万遍。


    推荐阅读


    上一篇：一般软件更新说的优化了更流畅了是指优化了算法吗

    下一篇：国风古乐点燃周庄夜经济 文化产业激发消费新活力