Откуда O (n ^ 2) берется в O (n ^ 2 * log n)?

Question

Не могли бы вы объяснить, как может выглядеть O (n ^ 2 * log n)?Я понимаю, O (n * log n) :

s=0
for(i=0; i<n; i++)
{
    for (j=1; j<n; j *= 2)
    {
        s=s+i*j;
    }

    s=s+1
}

, когда внешний цикл работает от 1 до n, равен O (n), а внутренний цикл повторяет log (n) раз завнешний цикл, например, j * = 2. Также я понимаю, что делает O (n ^ 2) (производительность прямо пропорциональна квадрату размера входных данных, например)

s=0
for(i=0; i<n; i++)
{
    for (j=0; j<n; j++)
    {
        s=s+i*j;
    }

    s=s+1
}

а что такое O (n ^ 2 * log n) ?Можете ли вы привести пример.

Answer 1

for(i=0; i<n; i++)
{
    for (int ij = 0; ij < n; ++ik) {
        for (j=0; j < ij; j *= 2)
        {
            s=s+i*j;
        }
    }
    s=s+1
}

Подумайте об этом так:

1. Мой ввод - n.
2. В первом цикле я перебираю каждый элемент из n, поэтому моя сложностьn
3. Таким образом, это означает, что во втором цикле я пересекаю каждый элемент ij n раз, моя сложность становится n*n
4. В третьем цикле я делаю логарифмическийОбход, который посещает logn элементов.Но каждый логарифмический обход выполняется n*n раз из предыдущих циклов, поэтому он становится n*n*logn

Answer 2

Вам нужно только добавить один цикл for снаружи.Это делает его O (n ^ 2 * log n) , потому что вы повторяете O (n * log n) n-раз .

for(int k=0; k<n; k++)
{
    s=0
    for(i=0; i<n; i++)
    {
        for (j=0; j<n; j *= 2)
        {
            s=s+i*j;
        }

        s=s+1
    }
}