Временная сложность алгоритма с двумя вложенными циклами - PullRequest
Новая
       11

Временная сложность алгоритма с двумя вложенными циклами

0 голосов
/ 14 октября 2018

Учитывая этот алгоритм: 

m = 1
while(a>m*b){
   m = m*2
}

while(a>=b){
   while(a>=m*b){
      a = a-m*b
   }
   m=m/2
}

Мой вопрос : Какова временная сложность этого алгоритма?

Что я сделал : Я должен найти количество инструкций.Итак, я обнаружил, что в первый раз примерно m = log_2 (a / b) итераций.Теперь для внутренней части второй части этого алгоритма я нашел следующую схему: a_i = a - i * m, где i - количество итераций.Так что для внутреннего while есть итерации a / bm.
Но я не знаю, как вычислить внешнее сейчас, потому что условие зависит от того, что внутреннее время сделало с a.

1 Ответ

0 голосов
/ 14 октября 2018

Давайте начнем с «нормализации» функции так же, как в вашем предыдущем вопросе , отметив, что все изменения в a и условия остановки снова пропорциональны b: 

n = a/b

// 1)
m = 1
while(n>m){
   m = m*2
}

// 2)
while(n>=1){
   while(n>=m){
      n = n-m
   }
   m=m/2
}

К сожалению, на этом сходство заканчивается ...

Фрагмент 1)

Обратите внимание, что m можно записать как целое число 2, поскольку оно удваивает каждый цикл: 

i = 0
while (n > pow(2, i)) {
   i++
}
// m = pow(2, i)

Из условия остановки:

enter image description here

Фрагмент 2)

Здесь m уменьшается прямо противоположным образом 1) , поэтому его снова можно записать как степеньиз 2: 

// using i from the end of 1)
while (n>=1) {
   k = pow(2, i)
   while (n >= k) {
      n = n - k
   }
   i--
}

Внутренний цикл проще, чем внутренний цикл из вашего предыдущего вопроса, потому что m не изменяется внутри него.Легко определить, сколько раз c он выполняет, а значение n в конце:

enter image description here

Этоточное определение оператора модуля % в "семействе C" языков: 

while (n>=1) {
   k = pow(2, i)
   n = n % k      // time complexity O(n / k) here instead of O(1)
   i--
}

Обратите внимание, что, поскольку последовательные значения k отличаются только в два раза2, ни при каких условиях значение n не будет больше или равно 2k;это означает, что внутренний цикл выполняет самое большее один раз для каждого внешнего цикла.Поэтому внешний цикл выполняется не более i х .

И первый, и второй циклы O(log n), что означает общую сложность времениO(log n) = O(log [a/b]).

Обновление: числовые тесты в Javascript, как и раньше. 

function T(n)
{
   let t = 0;

   let m = 1;
   while (n > m) {
      m *= 2; t++;
   }

   while (n >= 1) {
      while (n >= m) {
         n -= m; t++;
      }
      m/=2;
   }

   return t;
}

График T(n) против log(n) показывает хорошую прямую линию:

enter image description here

Редактировать: более подробное объяснение фрагмента 2) .

В конце фрагмента 1) , значение i = ceil(log2(n)) представляет количество значащих бит в двоичном представлении целого числа ceil(n).

Вычисление модуля целого числа с положительной степенью-of-2 2^i эквивалентно отбрасыванию всех, кроме первых i битов.Например: 

n     = ...00011111111   (binary)
m     = ...00000100000   (= 2^5)
n % m = ...00000011111
                 -----   (5 least significant bits)

Операция фрагмента 2) , таким образом, эквивалентна удалению старшего значащего бита n, по одному, пока не останется только ноль.Например: 

 outer loop no |           n
 ----------------------------
 1             | ...110101101
               |    ^
 2             | ...010101101
               |     ^
 3             | ...000101101
               |      ^
 4             | ...000001101
               |       ^ 
 :             | :
 :             | :
 i (=9)        | ...000000001
               |            ^
 ----------------------------
 final         |    000000000

Когда текущий старший значащий бит (на который указывает ^) равен:

  • 0 : внутренний цикл выполняет не выполняется, потому что значение n уже меньше k = 2^i (равно значению битовой позиции ^).
  • 1 : внутреннеецикл выполняется один раз , потому что n больше k, но меньше 2k (что соответствует биту выше текущей позиции ^).

Следовательно«худший» случай возникает, когда все значащие биты n равны 1, и в этом случае внутренний цикл всегда выполняется один раз.

Независимо от этого внешний цикл выполняется ceil(log2(n)) раз для любого значения n.

...