O(nm/8 * log(nm/8)) + O(nm/9 * log(nm/9)) +…+ O(nm/m * log(nm/m))等于什么？

Question

我很抱歉问题的标题，但我找不到一个更简单的方式来表达它。基本上，我的算法涉及O(nm/k)元素的快速排序，其中k的范围从8到m。我想知道这总的复杂性是多少，以及如何推导它？谢谢!

Answer 1

把除法放在对数中，我们得到nmlog(mn) * (1/8 + ... + 1/m) = O(nmlog(mn)log(m)) = O(mnlog(m)^2 + mnlog(m)log(n))。[我使用的事实是harmonic series

请注意，我们删除了对数中的除法，这意味着我们得到了一个上限，而不是确切的上限(但比取最大项乘以m的幼稚方法更好)。