Вычислительная сложность времени для двух блоков кода - PullRequest
Новая
       0

Вычислительная сложность времени для двух блоков кода

0 голосов
/ 09 февраля 2020

Код 1

Какова временная сложность T(n) приведенного ниже кода, если мы предположим, что n делится на 4? Может кто-нибудь объяснить мне это? 

for(int i=2;i<=n;i++)
{
  for(int j=0;j<=n;)
  {
    std::cout<<i<<" "<<j<<"\n";
    j=j+(n/4);
  }
}

Код 2

Какова сложность времени T(n) вложенных циклов ниже? Предположим, что n является степенью 2. То есть n = 2^k для некоторого натурального числа k. 

for (int i=1; i<=n; i++)
{
  j = n;
  while(j>=1)
  {
    <body of the while loop> //Needs θ(1)
    j=⌊j/2⌋; // ⌊⌋=>Floor function
  }
}

1 Ответ

2 голосов
/ 09 февраля 2020

Код 1 линейный. j += n / 4 означает, что внутренний l oop выполняется постоянное число раз (5) для любого значения n, а значение 5n уменьшается до O (n).

Код 2 - это O (n log (п)). Внешний l oop запускается n раз, а внутренний l oop запускается log2(n) раз, так как он многократно делит входные данные пополам.

...