Вопрос по math, algorithm, big-o, time-complexity – Определение времени выполнения больших циклов этих различных циклов?

18

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

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

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

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++;

Correct Answer: 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)

б) Для простоты предположим, что 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)

в) Для простоты предположим, что 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)

(Е)

 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)

(К)

  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)

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

Мой ответ: 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)

Question 4

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

a) True - since its bounded below by n^2 b) False - f(n) not strictly smaller than g(n) c) True d) True -bounded by n^10 e) False - f(n) not strictly smaller than g(n) f) True g) True h) false - since does not equal O(nlogn) i) true j) not sure k) not sure l) not sure - how should i even attempt these?*

Заранее спасибо.

Вы консультировались с книгой? Некоторые из них - самые основные случаи для анализа. dirkgently
Q2) wtf?i=i++ а такжеi * i, j++(запятая) goat
Хорошим обобщением является то, что если у вас есть три вложенных цикла, выполняющихся соответственно i, j и k раз, - у вас есть эффективность O (ijк). Если вы подумаете об этом, используя ту же логику, два вложенных цикла, каждый из которых выполняется n раз, дают O (n * n) = O (n ^ 2). С n-1 случаями и т. Д. Вы можете просто оценить его как n - большой O - верхняя граница nbrooks
казалось опечатки, исправлено. warpstar
Когда вы вычисляете время выполнения внутреннего цикла равным n ^ 2, вы уже учли временную эффективность внешнего цикла. Таким образом, вы не умножаете это на эффективность внешних контуров в конце проблемы ... это крайний двойной счет. nbrooks

Ваш Ответ

1   ответ
29

Давайте пройдемся по одному за раз.

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

My Answer: O(n)

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

Part (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;
}

My Answer: O(n)

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

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

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

My Answer: O(logn)

Не совсем. Заметить, чтоj все еще растет линейно, но цикл работает до тех пор, пока J2 & # X2264; п. Это означает, что как только j превысит & # x221A; n, цикл остановится. Следовательно, будет только O (& # x221A; n) итераций цикла, и, поскольку каждая из них выполняет O (1), общая выполненная работа составляет O (& # x221A; n).

Part (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;

My Answer: O(n^3)

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

Part (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++;

My Answer: O(n)

Ага! Абсолютно верно.

Part (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;

My Answer: O(n^4)

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

Part (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++;
 }

My Answer: O (n x log base 3 n? )

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

Part (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++;

My Answer: n x logn x log n = O(n log n^2)

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

Part (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;
}

My Answer: O(n^4)

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

Part (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++;

My Answer: O(n^3)

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

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

My Answer: O(n)

Это правильно!

Part (l)

Это странно, здесь нет части (l).

Part (m)
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; 
}

My Answer: O(n^3 log n)

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

n3 + n3 / 2+ n3 / 4 + n3 / 8 + ...

= n3 (1 + 1/2 + 1/4 + 1/8 + ...)

≤ 2n3

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

Question 4

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

f) True

Это на самом деле неверно. Выражение слева

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

которыйnot & # X3A9; (п2 & # x221A; n) = & # x3A9; (n5/2)

Для (j) обратите внимание, что log n6 = 6 log n. Это помогает?

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

Для (l) используйте тот факт, чтоlogb c = сlogba, Это помогает?

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

@ Гаррик Отличный улов! Исправлена.
часть (f) не должна быть O (n ^ 2), поскольку внешний цикл выполняется n раз, а внутренний цикл выполняется n, потому что 0 + n + 2n + 3n + ... + nx (x + 1) / 2 = n (1 + 2 + 3 + ..... x (x + 1) / 2) итого O (n ^ 2)
Похоже, что 0 + n + 2n + .... - это математический ряд, который эквивалентен результату, который я опубликовал выше ... Я не уверен насчет (n-1) n?
На мой взгляд, первая итерация внутреннего цикла выполняется 0 раз, вторая n раз, третья 2n раза и т. Д. Это означает, что общая выполненная работа составляет 0 + n + 2n + 3n + ... + ( n-1) n = n (0 + 1 + 2 + ... + n-1). Это n (n-1) n / 2 = тета (n ^ 3). Что-то не так с моими рассуждениями?
0 + 1 + 2 + ... + n-1 - это n (n-1) / 2, поэтому 0n + 1n + 2n + ... + (n-1) n = (0 + 1 + 2 + .. . + n-1) n = n (n-1) n / 2. Это неправильно? Кроме того, я думаю, что ваша серия неверна - последний член должен быть n (n-1), а не nx (x +1) / 2. Я не думаю, что вижу, что х здесь.

Похожие вопросы