Расчет сложности?

Question

Я пытался вычислить сложность следующей функции:

k=n;
while(k>0)
  g(n);
  k=k/2; {Comment: this is integer division, so 1/2=0}
end while;
for(j=0;j<m;j++)
  f(m);

В частности, сложность цикла while. Мне говорят, что сложность g(n) равна O(n), но я не уверен, какова будет сложность для него, и как я буду ее решать. Я пришел к выводу, что сложность не будет O(0,5n^2), но я не уверен, как рассчитать его, из-за каждого раза вдвое. У кого-нибудь есть идеи?

Answer 1

Если g (n) равно O(n), то ваша сложность равна O(n*log(n))

Чтобы объяснить далее, давайте игнорировать g (n) на данный момент

k = n;
while(k > 0) {
    k = k / 2;
}

Скажем, n = 1000

Тогда мы получим следующие значения k

Pass | k
-------------
 0   | 1000
 1   | 500
 2   | 250
 3   | 125
 4   | 62
 5   | 31
 6   | 15
 7   | 7
 8   | 3
 9   | 1
 10  | 0 (stopped)

log (1000) = 9,96. Обратите внимание, что потребовалось всего 10 итераций, чтобы снизить k до нуля. Это пример логарифмической (n) вычислительной сложности.

Затем, когда вы добавляете g (n) внутри цикла, это означает, что вы добавляете O (n) для каждой итерации, что дает нам общий итог O(n*log(n))

Answer 2

Сложность цикла while очевидна O(n log n), Есть log n итерации, потому что в конце каждой итерации k делится на 2. Чтобы получить количество итераций, выразите n как степень двух, скажем, 2^ х. Если 2^x=n, then x = log n, Вот почему сложность цикла while O(n log n), Не запутайтесь, потому что n не должен быть степенью 2, что подразумевает, что log n не всегда целое число, и вы должны написать вместо log n, [log n], где [y] является целой частью y, Вы всегда можете выразить [log n] как c* log nгде c - постоянная, которая не меняет сложности алгоритма. Поэтому вам не нужно [] функция и O(n log n) это приемлемый и правильный ответ.

Сложность цикла for зависит от сложности f(m), Если O(f(m)) O(1)тогда цикл равен O(m), но если O(f(m)) является O(m)то цикл O(m^2), Так как f(m) также является частью алгоритма, вам нужно знать сложность f() если вы хотите быть уверены в сложности всего кода.

Answer 3

Сложность вашего алгоритма:

Ваш первый цикл выполняется O(logn) раз, и каждая итерация должна выполнять g(n). Таким образом, требуется

O(sum{i from 0 to log(n)}{O(g(i))}). 

Второй цикл выполняется m раз. Занимает:

O(sum{j from 0 to m}{O(f(i))})

Общая сложность вашего алгоритма составляет:

O(sum{i from 0 to log(n)}{O(g(i))}) + O(sum{j from 0 to m}{O(f(i))})