我有一个算法,其时间复杂度的大O表示法如下:
log(N) + log(N+1) + log(N+2) + ... + log(N+M)
由于它是最大元素,所以是否与log(N+M)
相同?
还是因为它是M
个元素的总和,所以是M*log(N+M)
?
我有一个算法,其时间复杂度的大O表示法如下:
log(N) + log(N+1) + log(N+2) + ... + log(N+M)
由于它是最大元素,所以是否与log(N+M)
相同?
还是因为它是M
个元素的总和,所以是M*log(N+M)
?
更新: OP在评论中提出了另一个好问题。
如果我们只有两个看起来像Log(N) + Log(M+N)的项,那么我们可以将它们合并,并说它们肯定小于2 * Log(M+N),因此它们为O(Log (M+N))。如果我们有N + N^2 + N^3,它会缩小到只有N^3(最大元素),对吗?为什么我们不能在这里应用相同的逻辑——log(N+M) - 最大元素?
log(N+k)=log(N(1+k/N)) = log(N) + log(1+k/N) <= log(N) + log(2)
<= log(N) + log(N) <= 2 log(N)
所以
log(N) + log(N+1) + log(N+2) + ... + log(N+M) <= (M+1)2 log(N)
所以,大O表示法中的复杂度是:log(N)
回答你的问题:
1)是的,因为所有元素都少于或等于log(N+M)个固定数目。
2)实际上有M + 1个元素(从0到M)。
我要指出的是,O((M+1)log(N+M))是O(log(N))。
N + N^2 + N^3
,它将缩减为仅为N^3
(最大元素),对吗? 为什么我们不能在这里应用相同的逻辑 -log(N+M)
- 最大元素? - yerzhan7(N+M) log (N+M) - (N-1) log(N-1) - M + 1
。对此还有一些校正项,我没有进行严格评估。 - jwimberley