сложность кода

Question

в чем сложность программы, имеющей только один цикл, это log n? Может ли кто-нибудь дать мне несколько идей об оценке сложности кодов?

Answer 1

Ну, это действительно зависит от того, что происходит в этом цикле.

Этот цикл имеет линейное время, т. Е. O (n):

int sum = 0;
foreach( int i in SomeCollection )
{
    sum += i;
}

Однако рассмотрим циклкоторый выполняет поиск подстроки во время каждой итерации.Теперь вы должны рассмотреть сложность алгоритма поиска строки.На ваш вопрос нельзя ответить как есть.Вам понадобится предоставить пример кода, если вы хотите получить значимый ответ.

Answer 2

Сложность программного обеспечения

Существует область исследования, которая пытается количественно определить именно это.

Это называется цикломатическая сложность .

В этом случаеЯ полагаю, что ваш рейтинг сложности будет p = 2 , потому что цикл условный и это означает, что есть два пути через метод.

Сложность времени

Если выссылаются на сложность времени , это все равно просто O (1), если счетчик итераций цикла не получен с помощью полиномиальной или экспоненциальной функции, возможно, косвенно, потому что сам метод вызывается в более высоком цикле, или потому что циклСчетчик эффективно умножается на строковые операции или что-то на более низком уровне.

Answer 3

Чтобы понять сложность кода в Big-O, вам нужно спросить себя, «сколько выполнено итераций»?

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

Примеры:

For (i = 0 ; i < n ; i++ ) {
   //Do stuff
}

Это сложность

For (i = n ; i > 0 ; i= i/2 ) {
   //Do stuff
}

Это сложность ... Потому что в каждой итерации я делюсь пополам.

void Mess (int n) {
    for (i = 0 ; i < n ; i++) {
         //Do stuff
         Mess(n-1);
    } 
}

Теперь это выглядит как простой цикл, псих, потому что он вызывает себя с помощью рекурсии, на самом деле это просто беспорядок ... Каждая итерация вызывает себя n раз с n-1.
Так что тут было бы легче думать с конца. Если n == 1, есть 1 итерация. Если n == 2, то он вызывает предыдущий сценарий дважды.
Поэтому, если мы вызовем функцию , мы увидим, что получим это рекурсивно: Что в итоге, конечно, даст нам n!

Итог, это не всегда тривиально.

Answer 4

Вы можете легко предсказать время вычисления и сложность вашего кода с помощью некоторых инструментов, таких как "trend-prof" (https://pdfs.semanticscholar.org/8616/7f320e230641299754e0fbd860c44f5895f0.pdf)

. Для той же цели для кодов R, библиотека GuessCompx доступна в Github.

Answer 5

Если есть только один цикл, это, вероятно, количество раз, которое выполняется тело цикла .... Но, конечно, у вас может быть много скрытых циклов в вызовах библиотеки.Легко создать цикл, который будет выполняться n раз O(n^2) или хуже, если в теле цикла происходит strlen, memcpy и т. Д.

Или даже хуже, если у вас естьбиблиотека (или язык) с регулярными выражениями и их регулярное выражение наивны (как Perl), легко создать программу всего за один цикл O(2^n) !!Этого не может случиться с правильно написанной реализацией регулярного выражения.

Answer 6

Если это сложность времени Big-O, о которой вы спрашиваете, то для цикла она в n раз превышает сложность того, что находится внутри цикла, где n - предел числа циклов.

Итак.если для выполнения кода внутри цикла требуется постоянное время, т. е. если его временная сложность равна O (1), то сложность цикла будет O (1 * n) = O (n).

Inаналогичным образом, если внутри цикла у вас есть другой цикл, который будет делать m шагов, тогда весь ваш код будет O (n * m) и т. д.