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

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

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). Очевидно, что это всего лишь предположение, и любая помощь в выяснении того, как показать это математически, будет принята с благодарностью!


algorithm logarithm asymptotic-complexity
person chrismanderson    schedule 02.05.2011    source источник
comment
Сколько раз выполняется внутренний цикл? ceil((n-j)/log(n)). Работайте оттуда.   -  person Steve Jessop    schedule 03.05.2011

Ответы (3)


arrow_upward
0
arrow_downward

Здесь вы можете рассматривать 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) -- только представьте себе квадрат (куда я поставил .). Это постоянная часть двумерного прямоугольника (половина прямоугольника), поэтому O(a*b).

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

person ninjagecko    schedule 02.05.2011
comment
Спасибо - одно продолжение. Итак, n/log(n) — вы пришли к этому, просто взглянув, верно? Есть ли какой-нибудь другой трюк или предложение, чтобы различить n/log(n), кроме того, чтобы просто лучше разбираться в математике;)? Моя проблема всегда заключается в том, чтобы выяснить, как преобразовать код в математическое уравнение, и я часто удивляюсь тому, как мало помощи в Интернете по этому факту. - person chrismanderson; 03.05.2011
comment
Ну, это была константа по отношению к циклу (т. е. вы могли вытащить ее из суммы, если предпочитаете думать об этом таким образом). Если бы это было не log(n), а что-то вроде log(j) (по какой-то странной причине), это было бы сложнее. Я бы начал с того, что просто записал объем работы по срокам и попытался увидеть закономерность. Вы также можете смоделировать его, чтобы связать его (о, где-то между n и n ^ 2...). Вы можете переписать его рекурсивно и использовать en.wikipedia.org/wiki/Akra%E2. %80%93Bazzi_method - person ninjagecko; 03.05.2011

arrow_upward
0
arrow_downward

Вы можете довольно легко «просто подвести итог»:

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

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

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

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

person phimuemue    schedule 02.05.2011

arrow_upward
0
arrow_downward

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

введите здесь описание изображения

person Mohamed Ennahdi El Idrissi    schedule 25.04.2014