gpt4 book ai didi

algorithm - 循环的递归关系

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:27:34 25 4
gpt4 key购买 nike

题目是建立一个递归关系,求出算法给出的值。答案应该是 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++

最佳答案

不完全确定,但这里是。

第二个循环执行 1 - sqrt(1) + 2 - sqrt(2) + ... + n - sqrt(n) = n(n+1)/2 - n^1.5次 => O(n^2) 次。参见 here对于 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)

关于algorithm - 循环的递归关系,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3978425/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com