计算成本 [英] 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屋!
查看全文