Как определить временную сложность кода ниже - PullRequest
Новая
       74

Как определить временную сложность кода ниже

0 голосов
/ 04 апреля 2020 
public void test(int n)
{
   for(i=1;i<=n;i=i*2)
  {
     for(j=1;j<n;j=j+(j*i))
      {
         // some code
      }
  }
}

Над кодом есть два l oop. Внешние l oop, которые выполняют log (n) раз. Как мы можем рассчитать, сколько раз внутренний l oop выполнит? Какова будет временная сложность вышеуказанного кода?

1 Ответ

2 голосов
/ 04 апреля 2020

Внутренний l oop занимает время log_ {i + 1} (n) (основание журнала i + 1 из n). Предполагая, что n является степенью 2, и, используя изменение базовой формулы, преобразовать в базовую 2: log_ {i + 1) (n) = lg (n) / lg (i + 1), что означает «некоторый код». будет выполнено много раз: lg (n) / lg (2) + lg (n) / lg (3) + lg (n) / lg (5) + ... + lg (n) / lg (n) +1).

Теперь 1 / lg (2) + 1 / lg (3) + ... + 1 / lg (n + 1) <= 1 + 1 / lg (2) + 1 / lg (4) + ... 1 / lg (n) = 1 + 1/1 + 1/2 + 1/3 + ... + 1 / lg (n) ~ = (1 + log (lg (n) ))). </p>

Аналогично 1 / lg (2) + 1 / lg (3) + ... + 1 / lg (n + 1)> = 1 / lg (4) + 1 / lg (8) + ... + 1 / lg (2n) ~ = (log (lg (2n)) - 1). (Используя приближение к гармоническим c числам: H (n) ~ = log (n)).

Таким образом, кажется, что сложность состоит в log (n) log (log (n)).

Это довольно схематичное доказательство, но, надеюсь, укажет вам правильное направление.

...