对于TimeComplexity分析ima需要帮助总结

-1

对于算法时间复杂度分析，我需要知道当我从1运行到logn时，函数n/i的总和的结果是什么，我看到了某个可信任的地方谐波相加，而是我高度怀疑它...对于TimeComplexity分析ima需要帮助总结

该算法的功能最初是T（N）= 5T（N/5）+ N/LOGN

这个问题最初发现在介绍算法第二版书

救救我吧！ :)

在第58页，有一行说：

= N *西格玛N/I其中i从1到LOGN

= N *西格玛1 /我在那里我从1到logn

多数民众赞成那是唯一的一部分，我有问题....导致他们所做的只是采取了西格玛的n，但它去了哪里？为什么只是让它消失？

，而不是他们在说什么，我想应该是这样：

= N *西格玛N/I其中i从1到LOGN

= N * N *西格玛1 /我其中i从1到LOGN

= N^2 *西格玛1/I，其中i从1到LOGN

2011-08-28 Ofek Ron

答案是'数学错误'，对于'n/0'，第一个元素。你的意思是从1到logn？ – amit

其开始于1 srry –

这的确是谐波之和：

n/1 + n/2 + ... + n/logn = n* [ 1 + 1/2 + ... + 1/logn] = n*H(logn)其中H(logn)是logn harmonic number。

该书使用H(m) = theta(logm)，正因为如此，H(logn) = theta(loglogn)。所以总体上我们得到：T(n) = n*H(logn) = n*theta(loglogn) = theta(n*loglogn)。

2011-08-28 12:39:15 amit

我同意你的意见，但是然后你得到O（nlogn）不是O（logn）就像你会得到刚才的谐波图 –

编辑原始问题plz参考改变... –

@Ofek罗恩：看看我的编辑，这本书使用H（m）= theta（logm）'，它用它来说'T（n）= n * H（logn）= n * theta（loglogn）= theta（n * loglogn）' – amit

回答