计算成本 [英] Computational cost

问题描述

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

  while（n> 2）
n = sqrt（n）; 
 
 while（n> 2）
 n = log（n）; 
  

解决方案

第二个是 O （log * n）其中 log * 是迭代对数。

分析第一个对象得到如下结果：

<$ （sqrt（n））= n ^（1/4）
sqrt（sqrt（sqrt（n） （n）））= n ^（1/8）
...
sqrt apply k times = n ^（1/2 ^ k）
/ pre>

考虑第一个算法执行 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 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屋！