Добавление лога в асимптотический анализ

Question

Возникла проблема, через которую я пытаюсь разобраться, и очень признателен за помощь!Какова временная сложность ...

for (int j = 1 to n) {
    k = j;
    while (k < n) {
        sum += a[k] * b[k];
        k += log n;
    }
}

Внешний цикл for выполняется n раз.Я не уверен, как бороться с k+= log n во внутреннем цикле.Я думаю, что это O (n ^ 2).Добавление log (n) к k не дает дополнительных n циклов, но я думаю, что оно меньше, чем O (n * log n).Очевидно, это всего лишь предположение, и любая помощь в выяснении, как показать это математически, будет принята с благодарностью!

Answer 1

Вы можете довольно просто "просто подать":

Внешний цикл имеет, как вы сказали, n шагов. Внутренний цикл имеет (k-j) / log n шагов.

Это (примерно):

 n
---
\     (n-j)             n*n
/   -------- = ... = ---------
___  (log n)          2*log(n)
j=1

Итак, всего O((n^2)/log(n)).

Answer 2

Формально вы можете действовать следующим образом:

Answer 3

Здесь вы можете трактовать log(n) как константу, вроде.

Каждая итерация цикла будет выполнять постоянный объем работы (sum+=...; k+=...) несколько раз, равный n /log(n).Есть n итераций цикла.Таким образом, общая работа составляет n^2 / log(n).

Каждый раз, когда вы видите несколько операций, например:

 ---------------------b-------------------------
 |O(blah) + O(blah) + O(blah) + O(blah) + O(blah)
 |O(blah) + O(blah) + O(blah) + O(blah)     .
a|O(blah) + O(blah) + O(blah)               .
 |O(blah) + O(blah)                         .
 |O(blah)     .         .         .         .

Это a*b * O(blah) - просто представьте квадрат (куда я положил. с).Это постоянная часть 2D-прямоугольника (половина прямоугольника), следовательно, O(a*b).

. В приведенном выше случае b = n, a = n/log(n) и O (бла)= O(1) (из внутреннего цикла)