计算成本 [英] Computational cost

问题描述

有没有人，知道什么是计算成本这两块code是？

，而（N大于2）    N =开方（N）; 而（正→2）    N =的log（n）;

解决方案

第二是 O（日志* N），其中日志* 的重对数。

浅析第一个产生这样的：

 的sqrt（N）= N ^（1/2）
的sqrt（SQRT（n））的=正^（1/4）
的sqrt（SQRT（SQRT（n））的）= N ^（1/8）
...
的sqrt施加k次=正^（1/2 ^ k）的
 

认为，第一种算法执行时 K 倍（基本上，我们要申请的次数开方，直到 N'LT; = 2 ）

考虑这样一个道理：

  N R个（1/2 ^ K）= P（P＆LT; = 2）| ^（2 ^ k）的
N = P ^（2 ^ K）|登陆
登录N =（2 ^ K）的log P |登陆
日志日志N =日志（2 ^ K）+日志的log P
日志日志N = klog2 +日志的log P
=＆GT; K〜=登录日志N
 

所以第一种算法是 O（日志日志N）。

Is there someone that knows what the computational cost for this two pieces of code is?

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

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

解决方案

The second would be O(log* n) where log * is the iterated logarithm.

Analysing the first one yields something like this:

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)

Consider that the first algorithm executes k times (basically, the number of times we have to apply sqrt until n <= 2).

Consider this reasoning:

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

So the first algorithm is O(log log n).

这篇关于计算成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！