循环的递归关系

发布于 2024-09-28 10:53:50 字数 194 浏览 1 评论 0原文

问题是建立一个递归关系来找到算法给出的值。答案应该是 teta() 术语。

foo = 0;

for int i=1 to n do
    for j=ceiling(sqrt(i)) to n do
        for k=1 to ceiling(log(i+j)) do
             foo++

原文

The question is to set up a recurrence relation to find the value given by the algorithm. The answer should be in teta() terms.

foo = 0;

for int i=1 to n do
    for j=ceiling(sqrt(i)) to n do
        for k=1 to ceiling(log(i+j)) do
             foo++

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

時窥 2024-10-05 10:53:50

不完全确定，但就这样。

第二个循环执行 1 - sqrt(1) + 2 - sqrt(2) + ... + n - sqrt(n) = n(n+1)/2 - n^1.5 次 => ; O(n^2) 次。请参阅此处，了解 sqrt(1) + ... + sqrt(n) = O(n^1.5)。

我们已经确定第三个循环将被触发 O(n^2) 次。因此，该算法渐近等价于如下所示：

for i = 1 to n do
    for j = 1 to n do
        for k = 1 to log(i+j) do
            ++foo

这导致总和 log(1+1) + log(1+2) + ... + log(1+n) + ... + log( n+n)。 log(1+1) + log(1+2) + ... + log(1+n) = log(2*3*...*(n+1)) = O(n log n ）。该值乘以 n，结果为 O(n^2 log n)。

所以你的算法也是O(n^2 log n)，如果我没记错的话，也是Theta(n^2 log n)。

Not entirely sure but here goes.

Second loop executes 1 - sqrt(1) + 2 - sqrt(2) + ... + n - sqrt(n) = n(n+1)/2 - n^1.5 times => O(n^2) times. See here for a discussion that sqrt(1) + ... + sqrt(n) = O(n^1.5).

We've established that the third loop will get fired O(n^2) times. So the algorithm is asymptotically equivalent to something like this:

for i = 1 to n do
    for j = 1 to n do
        for k = 1 to log(i+j) do
            ++foo

This leads to the sum log(1+1) + log(1+2) + ... + log(1+n) + ... + log(n+n). log(1+1) + log(1+2) + ... + log(1+n) = log(2*3*...*(n+1)) = O(n log n). This gets multiplied by n, resulting in O(n^2 log n).

So your algorithm is also O(n^2 log n), and also Theta(n^2 log n) if I'm not mistaken.

回复收藏 0 原文

~没有更多了~