算法复杂度 O(n*log(n))- 我们需要除以 2 吗？

Question

在 O(n log(n)) 的许多定义中，我通常认为子问题必须是原始问题大小除以二的要求。但是，特别是，我已经看到 O(log(n)) 只需要是减小大小的问题。

我们一定要把问题分成两半才能得到nlog(n)的问题吗？

或者这仅仅是一个还原问题？像这样：

for (i = 0; i < A.length(); i++)
{
    for (j = i; j < A.length(); j++)
    {
        //do something
    }
}

像这样的东西也可以归类为 n(log(n)) 吗？还是更接近 O(n^2)？

Answer 1

除以任何其他常数也会给你 log(n) 复杂度。那是因为你可以转换log bases，当你对Big-O感兴趣时，常量就会消失。

你会注意到分母是一个常数。

Answer 2

显示的代码是O(n^2)

外循环决定内循环的迭代次数。 N + N-1 + N-2 + N-3 + ... + 1 = O(n^2)

要获得 log(n) 的复杂度，您需要在每次迭代中去掉 cn 元素。其中 0<c<1

Algorithmic complexity O(n*log(n))- Do we need to divide by 2?