Мне нужна помощь, чтобы понять, как найти большой сегмент кода

Question

Мне нужна помощь, чтобы понять, как найти большой сегмент кода

Завтра у меня финал Computer Science II, и мне нужна помощь в понимании того, как найти Big-Oh для сегментов кода. Я искал в интернете и не смог найти примеров того, как мне нужно это понимать.

Вот проблема из нашего финального примера:

for(int pass = 1; i <= n; pass++)
{
for(int index = 0; index < n; index++)
for(int count = 1; count < n; count++)
{
//O(1) things here.
}
}
}

Мы должны найти порядок (Big-Oh) алгоритма.

я считать что это будет O (n ^ 3), и вот как я пришел к такому выводу

for(int pass = 1; i <= n; pass++) // Evaluates n times
{
for(int index = 0; index < n; index++) // Evaluates n * (n+1) times
for(int count = 1; count < n; count++) // Evaluates n * n * (n) times
{
//O(1) things here.
}
}
}
// T(n) = (n) + (n^2 + n) + n^3
// T(n) = n^3 + n^2 + 2n
// T(n) <= c*f(x)
// n^3 + n^2 + 2n <= c * (n^3)
// O(n) = n^3

Я просто не уверен, правильно ли я это делаю. Может кто-нибудь объяснить, как оценить код, подобный этому, и / или подтвердить мой ответ?

5

algorithm analysis c++order

Решение

Другие решения

Вы абсолютно правы. Это O (n ^ 3) для вашего примера.

Чтобы найти время выполнения Big Oh любого сегмента кода, вы должны подумать о том, сколько раз фрагмент кода выполняет O (1).

Позвольте мне упростить ваш пример, чтобы дать лучшее представление об этом:

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times
for(int count = 1; count < n; count++) // Evaluates n * n * (n) times
{
//O(1) things here.
}
}

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

Еще одна вещь, о которой нужно позаботиться, это то, что Большой О — это верхний предел. Это означает, что вы всегда должны думать о том, что произойдет с кодом, когда у вас большой ввод (в вашем случае, большое значение n, Еще одним следствием этого факта является то, что умножение или сложение по константам не влияет на границу Большого О. Например:

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times
for(int count = 1; count < 2*n; count++) // Runs 2*n times
{
//O(1) things here.
}
}

Время выполнения большого О этого кода также равно O (n ^ 2), поскольку O (n * (2n)) = O (n ^ 2).

Также проверьте это: http://ellard.org/dan/www/Q-97/HTML/root/node7.html

0

Источник

Accepted Answer

Да, это O(n^3), Тем не мение:

for(int pass = 1; pass <= n; pass++) // Evaluates n times
{                 //^^i should be pass

for(int index = 0; index < n; index++) //Evaluates n times
for(int count = 1; count < n; count++)  // Evaluates n-1 times
{
//O(1) things here.
}
}
}

Поскольку у вас есть три слоя вложенных циклов, вложенный цикл будет оценен n *n * (n-1) раз, каждая операция внутри самого внутреннего цикла for занимает O (1) времени, так что в общей сложности у вас есть n^3 - n^2 постоянные операции, которые O(n^3) в порядке роста.

Хорошее резюме того, как измерить порядок роста в обозначениях Big O, можно найти здесь:

Big O Notation MIT

Цитирование части из приведенного выше файла:

Вложенные циклы
 for I in 1 .. N loop
for J in 1 .. M loop
sequence of statements
end loop;
end loop;
Внешний цикл выполняется N раз. Каждый раз, когда выполняется внешний цикл, внутренний цикл
выполняет M раз. В результате операторы во внутреннем цикле выполняют всего N * M
раз. Таким образом, сложность O (N * M).
В частном частном случае, когда условие остановки внутреннего цикла J <N вместо
из J <M (т.е. внутренний цикл также выполняется N раз), общая сложность для двух циклов составляет O (N ^ 2).

Аналогичное обоснование может быть применено в вашем случае.

2