c/c++语言开发共享计算成本

是否有人知道这两段代码的计算成本是多少?

while (n > 2) n = sqrt(n); while (n > 2) n = log(n); 

    第二个是O(log* n) ,其中log *是迭代对数 。

    分析第一个产生这样的东西:

     sqrt(n) = n ^ (1/2) sqrt(sqrt(n)) = n ^ (1/4) sqrt(sqrt(sqrt(n))) = n ^ (1/8) ... sqrt applied k times = n ^ (1/2^k) 

    考虑第一个算法执行k次(基本上,我们必须应用sqrt直到n <= 2 )。

    考虑这个推理:

     n ^ (1/2^k) = p (p <= 2) | ^ (2^k) n = p ^ (2^k) | log log n = (2^k) log p | log log log n = log (2 ^ k) + log log p log log n = klog2 + log log p => k ~= log log n 

    所以第一个算法是O(log log n)

    如果在日志域中重写它,第一个答案应该变得明显:

     n = log2(n); while (n > 1) n = n / 2; 

    您需要将一个数字减半才能达到1? O(log n)。

      以上就是c/c++开发分享计算成本相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。

      www.ctvol.com true Article c/c++语言开发共享计算成本

      本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

      ctvol管理联系方式QQ:251552304

      本文章地址:https://www.ctvol.com/c-cdevelopment/559919.html

      (0)
      上一篇 2021年1月27日 上午11:48
      下一篇 2021年1月27日 上午11:51

      精彩推荐