Определение времени выполнения больших-O этих разных циклов?

У меня есть ряд вопросов, в которых мне нужны отзывы и ответы. Я буду комментировать, что я думаю, это не домашнее задание, а скорее подготовка для моего экзамена.

Моя основная проблема заключается в определении итераций цикла для разных случаев. Как бы попытаться понять это?

Оценка времени выполнения.

Q2.

 for(int i =0 ; i < =n ; i++) // runs n times
   for(int j =1; j<= i * i; j++) // same reasoning as 1. n^2
      if (j % i == 0)
         for(int k = 0; k<j; k++) // runs n^2 times? <- same reasoning as above.
            sum++;

Правильный ответ: N × N2 × N = O (N ^ 4)

Для следующих Вопросов ниже, у меня нет правильных ответов.

Q3. а)

     int x=0; //constant
     for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
         x=x+2*i;

Мой ответ: O (n)

b) Предположим для простоты, что n = 3 ^ k

    int z=0;
    int x=0;
    for (int i=1; i<=n; i=i*3){ // runs n/3 times? how does it effect final answer?
       z = z+5;
       z++;
       x = 2*x;
    }

Мой ответ: O (n)

c) Предположим для простоты, что n = k ^ 2,

   int y=0; 
   for(int j=1; j*j<=n; j++) //runs O(logn)?  j <= (n)^1/2
   y++; //constant

Мой ответ: O (logn)

г)

  int b=0; //constant
  for(int i=n; i>0; i--) //n times
    for(int j=0; j<i; j++) // runs n+ n-1 +...+ 1. O(n^2) 
      b=b+5;

Мой ответ: O (n ^ 3)

(е)

 int y=1;
 int j=0;
 for(j=1; j<=2n; j=j+2) //runs n times
    y=y+i;
 int s=0;
 for(i=1; i<=j; i++) // runs n times
 s++;

Мой ответ: O (n)

(f)

 int b=0;
 for(int i=0; i<n; i++) //runs n times
   for(int j=0; j<i*n; j++) //runs n^2 x n times? 
      b=b+5;

Мой ответ: O (n ^ 4)

(g) Предположим для простоты, что n = 3k, для некоторого натурального k.

   int x=0;
   for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i. 
     if(i%2 != 0) //will always be true for values above
      for(int j=0; j<i; j++) // runs n times
        x++;
    }

Мой ответ: O (n x log base 3 n?)

(h) Предположим для простоты, что n = k2, для некоторого натурального k.

   int t=0;
   for(int i=1; i<=n; i++) //runs n times
      for(int j=0; j*j<4*n; j++) //runs O(logn)
         for(int k=1; k*k<=9*n; k++) //runs O(logn)
            t++;

Мой ответ: n x logn x log n = O (n log n ^ 2)

(i) Предположим для простоты, что n = 2s, для некоторого натурального s.

   int a = 0;
   int k = n*n;
     while(k > 1) //runs n^2
     {
       for (int j=0; j<n*n; j++) //runs n^2
          { a++; }
        k = k/2;
    }

Мой ответ: O (n ^ 4)

(j)

  int i=0, j=0, y=0, s=0;
  for(j=0; j<n+1; j++) //runs n times
     y=y+j; //y equals n(n+1)/2 ~ O(n^2)
  for(i=1; i<=y; i++) // runs n^2 times
     s++;

Мой ответ: O (n ^ 3)

(к)      int я = 1, z = 0;      в то время как (z < n * (n + 1)/2) {//арифметическая серия, выполняется n раз         г + = я; я ++;       }

Мой ответ: O (n)

(m) Предположим для простоты, что n = 2s, для некоторого натурального s.

  int a = 0;
  int k = n*n*n;
  while(k > 1) //runs O(logn) complexity
   {
     for (int j=0; j<k; j++) //runs n^3 times
      { a--; }
     k = k/2; 
    }

Мой ответ: O (n ^ 3 log n)

Вопрос 4

http://i.stack.imgur.com/zMkt7.jpg

  • a) Истинный - поскольку его ограниченный снизу на n ^ 2
  • b) False - f (n) не строго меньше g (n)
  • c) True
  • d) True-bounded by n ^ 10
  • e) False - f (n) не строго меньше g (n)
  • f) True
  • g) True
  • h) false - поскольку не равно O (nlogn)
  • i) true
  • j) не уверен
  • k) не уверен
  • l) не уверен - как я должен это делать? *

Спасибо заранее.

Ответы

Ответ 1

Пройдите через эти по очереди.

Часть (a)

 int x=0; //constant
 for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
     x=x+2*i;

Мой ответ: O (n)

Оп! Это правильно. Цикл запускает O (n) раз и работает O (1) на итерацию.

Часть (b)

int z=0;
int x=0;
for (int i=1; i<=n; i=i*3){ // runs n/3 times? how does it effect final answer?
   z = z+5;
   z++;
   x = 2*x;
}

Мой ответ: O (n)

Не совсем. По мере того, как цикл прогрессирует, подумайте о значениях i. Он примет ряд значений 1, 3, 9, 27, 81, 243,..., 3 k. Так как i утроится на каждой итерации, он принимает последовательные степени три.

Цикл, очевидно, только O (1) работает на итерацию, поэтому главный вопрос заключается в том, сколько будет точных итераций. Цикл остановится, когда i > n. Если мы допустим k некоторую произвольную итерацию цикла, значение i на итерации k будет 3 k. Петля останавливается, когда 3 k > n, что происходит, когда k > log 3 n. Поэтому число итераций - только O (log n), поэтому общая сложность O (log n).

Часть (c)

int y=0; 
for(int j=1; j*j<=n; j++) //runs O(logn)?  j <= (n)^1/2
    y++; //constant

Мой ответ: O (logn)

Не совсем. Обратите внимание, что j растет линейно, но цикл работает до тех пор, пока j 2 & le; п. Это означает, что как только j превышает & radic; n, цикл остановится. Следовательно, будут только итерации O (& radic; n) цикла, и поскольку каждая из них выполняет O (1), общая работа выполнена O (& radic; n).

Часть (d)

int b=0; //constant
for(int i=n; i>0; i--) //n times
   for(int j=0; j<i; j++) // runs n+ n-1 +...+ 1. O(n^2) 
      b=b+5;

Мой ответ: O (n ^ 3)

Не совсем. На самом деле вы вдвойне считаете, что нужно много работы. Вы правы, что внутренний цикл будет запускать n + (n-1) + (n-2) +... + 1 раз, что является O (n 2) раза, re уже суммируя все итерации внешнего цикла. Вам не нужно умножать это значение на O (n) еще раз. Наиболее точным ответом будет O (n 2).

Часть (e)

int y=1;
int j=0;
for(j=1; j<=2n; j=j+2) //runs n times
   y=y+i;

int s=0;
for(i=1; i<=j; i++) // runs n times
   s++;

Мой ответ: O (n)

Оп! Правильно.

Часть (f)

int b=0;
for(int i=0; i<n; i++) //runs n times
    for(int j=0; j<i*n; j++) //runs n^2 x n times? 
       b=b+5;

Мой ответ: O (n ^ 4)

Опять же, я считаю, что вы переполнены. Внутренний цикл будет запускать 0 + n + 2n + 3n + 4n +... + n (n-1) = n (0 + 1 + 2 +... + n - 1) раз, поэтому общая работа выполнена О (п 3). Вы не должны умножаться на количество циклов, выполняемых внешним циклом, потому что вы уже суммируете все итерации. Наиболее точным временем выполнения будет O (n 3).

Часть (g)

int x=0;
for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i. 
   if(i%2 != 0) //will always be true for values above
      for(int j=0; j<i; j++) // runs n times
         x++;
 }

Мой ответ: O (n x log base 3 n?)

Внешний цикл здесь действительно запустит O (log n) раз, но покажите, сколько работы выполняет внутренний цикл. Вы правы, что оператор if всегда оценивает значение true. Это означает, что внутренний цикл будет работать 1 + 3 + 9 + 27 +... + 3 log 3 n. Это суммирование, однако, выполняется для (3 log 3 n + 1 - 1)/2 = (3n + 1)/2. Поэтому общая работа, проделанная здесь является просто O (n).

Часть (h)

int t=0;
for(int i=1; i<=n; i++) //runs n times
   for(int j=0; j*j<4*n; j++) //runs O(logn)
      for(int k=1; k*k<=9*n; k++) //runs O(logn)
         t++;

Мой ответ: n x logn x log n = O (n log n ^ 2)

Не совсем. Посмотрите на второй цикл. Это фактически работает O (& radic; n) раз, используя ту же логику, что и одна из ранних частей. В этом третьем внутреннем цикле также выполняются O (& radic; n) раз, поэтому общая работа будет O (n 2).

Часть (i)

int a = 0;
int k = n*n;
while(k > 1) //runs n^2
{
    for (int j=0; j<n*n; j++) //runs n^2
       { a++; }
     k = k/2;
}

Мой ответ: O (n ^ 4)

Не совсем. Внешний цикл начинается с k, инициализированного до n 2 но обратите внимание, что k уменьшается на половину на каждой итерации. Это означает, что число итераций внешнего цикла будет log (n 2) = 2 log n = O (log n), поэтому внешний цикл запускает только O (log n) раз. Этот внутренний цикл делает O (n 2), поэтому общая продолжительность выполнения - O (n 2 log n).

Часть (j)

int i=0, j=0, y=0, s=0;
for(j=0; j<n+1; j++) //runs n times
   y=y+j; //y equals n(n+1)/2 ~ O(n^2)
for(i=1; i<=y; i++) // runs n^2 times
   s++;

Мой ответ: O (n ^ 3)

Закрыть, но не совсем! Первый цикл выполняется во времени O (n), и к моменту его выполнения значение j равно & Theta; (n 2). Это означает, что второй цикл выполняется для времени & Theta; (n 2), поэтому общее время, затраченное на это, равно & theta; (n 2).

Часть (k)

 int i=1, z=0;
 while( z < n*(n+1)/2 )//arithmetic series, runs n times
 {
       z+=i; i++;
 }

Мой ответ: O (n)

Правильно!

Часть (l)

Это нечетное, нет части (l).

Часть (м)

int a = 0;
int k = n*n*n;
while(k > 1) //runs O(logn) complexity
{
   for (int j=0; j<k; j++) //runs n^3 times
   { a--; }
   k = k/2; 
}

Мой ответ: O (n ^ 3 log n)

Закрыть, но не совсем. Вы правы, что внешний цикл запускает O (log n) раз и что внутренний цикл делает O (n 3) работают на первой итерации. Однако посмотрите на число итераций внутреннего цикла:

n 3 + n 3/2+ n 3/4 + n 3/8 +...

= n 3 (1 + 1/2 + 1/4 + 1/8 +...)

& ле; 2n 3

Таким образом, общая работа, выполняемая здесь, на самом деле является только O (n 3), хотя существуют итерации log n.

Вопрос 4

Ваши ответы правильны, за исключением следующих:

f) True

Это фактически неверно. Выражение слева

(3/2) n 3/2 + 5n 2 + lg n

который не & Omega; (n 2 & radic; n) = & Omega; (n 5/2)

Для (j) заметим, что log n 6= 6 log n. Помогает ли это?

Для (k) спросите, являются ли обе стороны O и & Omega; друг друга. Что вы находите?

Для (l) используйте тот факт, что a log b c= c log b a. Помогает ли это?

Надеюсь, это поможет!