Как рассчитать Big O этого алгоритма?

Question

Я хочу вычислить Big O из x++ в приведенном ниже алгоритме.

for (int i = 2;i < n;i*=2)
    for(int j = i;j < m;j*=j)
       x++;

Я много об этом думаю, но не могу решить.Как я могу решить это?

Answer 1

O(lg(n) * lg(lg(m)))

самое большее lg(n) для внешнего цикла и lg(lg(m)) для другого.

РЕДАКТИРОВАТЬ: больше помочь доказать:

позволяет изменить переменные:

nn = lg(n);
mm = lg(m);

код станет:

for (int i = 1;i < nn;i++)
    for(int j = i;j < mm;j *= 2)
        x++;

теперь время выполнения будет O(nn * lg(mm)).

РЕДАКТИРОВАТЬ (2): границы могут стать более узкими (потому что у нас j = i во втором цикле, а не j = 1)

если nn >= mm, то (x++) = theta(mm * lg(mm)) = theta(lg(m) * lg(lg(m)))

и

если nn < mm, то (x++) = theta(nn * lg(mm)) = theta(lg(n) * lg(lg(m)))

Answer 2

Очевидно, что внешний цикл равен O (log ₂ ( n )), так как i удваивается с каждой итерацией от 2 до n эксклюзив. Итак:

2 ^x <<em> n
⇔ log ₂ (2 ^x ) 2 ( n )
10 x 2 ( n )

Таким образом, требуется не более log ₂ ( n ) итераций внешнего цикла до тех пор, пока i < n больше не будет выполнено, поэтому O (log ( n * 1045) *)).

Внутренняя часть немного хитрая, поскольку текущее значение i внешнего цикла используется для инициализации j внутреннего цикла. Кроме того, j умножается на себя (т. Е. j ² ) с каждой итерацией. Итак:

j ^{2 x} <<em> m
⇔ log _j ( j ^{2 x} ) J ( м )
⇔ 2 ^x j ( m )
⇔ log ₂ (2 ^x ) 2 (log _j ( м ))
11 x 2 (log _j ( m ))

Таким образом, требуется не более log ₂ (log _j ( m )) итераций внутреннего цикла до выполнения условия j < m больше не выполняется, поэтому O (log (log ( m ))). И если мы игнорируем базы, мы можем оценить общую сложность в O (log ( n ) · log (log ( m ))).

Answer 3

O(log(n) * log log(m)) внутренняя часть получает выполненный журнал регистрации m раз.

Answer 4

Я попытался методично вывести порядок роста сложности вашего алгоритма.К сожалению, я не мог сделать это с j, который меняется на каждой итерации внутренней петли.

Тем не менее, я придумал формулу с постоянным коэффициентом k вместо j.

Ваш алгоритм, согласно моему предложению, должен выглядеть следующим образом:

for (int i = 2;i < n;i*=2)
    for(int j = i;j < m;j*=k)
       x++;

Решение состоит в следующем:

Тем временем я попытаюсь найти решение, точно соответствующее вашей первоначальной проблеме.