структура данных - время выполнения - PullRequest
0 голосов
/ 31 августа 2010

Просто путаница .... Часть примера кода на C ++ выглядит следующим образом


Я просто заново отредактировал весь пост. Извините за путаницу

int i, j;   
i = 0;    // c1
j = 0;    // c2
while (i < n)   // (n+1)c3
{
  i++;   // n c4
   while ( j < i)  // (2+3+....+n+(n+1)c5
   {
     j++;   // (1+2+...+n)c6
   }
  j = 0;  // c7
}

Очевидно, что c1, c2 и c7 постоянны. Мы не заинтересованы в них, и они не имеют большого значения для определения времени работы.

Чего я не понимаю, так это c5 и c6.

Почему это 2 + 3 + 4 ... + n + (n + 1) для c5? Почему он начинается с 2, а не с 1 + 2 + 3 ... + (n + 1) ??? Обратите внимание, что мы можем переписать C5 -> (n * (n-1) / 2) + n

Для c6 эта комбинация может быть переписана как n * (n-1) / 2

Первоначально я думал, что C6 - это n, потому что C6 зависит от двух условий: первого цикла while и второго цикла while. Но поскольку j всегда будет возвращаться к 0, мы действительно зависим от первого цикла while. Поскольку n

n = 3

0 <3, 1, 0 <1, 1, 0 </p>

1 <3, 2, 0 <1, 1, 0 </p>

2 <3, 3, 0 <1, 1, 0 </p>

3 <3. </p>

Может кто-нибудь, пожалуйста, подробно объяснить, как определяются C5 и C6? Извините, если эта проблема звучит глупо для экспертов Спасибо!

Ответы [ 2 ]

4 голосов
/ 31 августа 2010

Здесь у вас есть время выполнения 2n. Каждый раз i увеличивается, j на единицу меньше, поэтому внутренний цикл выполняется ровно один раз.

i=0, j=0 // init
i=1, j=0 // outer loop
i=1, j=1 // inner loop
i=2, j=1 // outer loop
i=2, j=2 // inner loop

Более типично, вы бы сбросили j на 0 во внешнем цикле. В этом случае у вас будет время выполнения n*(n-1)/2

3 голосов
/ 31 августа 2010

Я не совсем понимаю ваш вопрос, но мне кажется, что вам нужно переместить инициализацию j внутри цикла:

while (i < n)   
{
    j = 0;    // <--- here
    i++;   
    // etc...
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...