Какова наихудшая временная сложность этого алгоритма?

void intFunction (int n, int value) 
{ 
    int b,c; 
    for (int j = 4; j < n; j++) { 
      for (int i = 0; i < j; i++) { 
       b *= val; 
       for (int k = 0; k < n; ++k) 
        c += b; 
      } 
    } 
}

Я только что узнал понятие Big-O. поэтому для этого кода, по моему мнению, время выполнения внешнего цикла равно n, а второе внутреннее - n (n + 1)/2, а внутреннее - n (n + 1)/2. поэтому время работы будет O (N^5)? я прав?Какова наихудшая временная сложность этого алгоритма?

источник

2014-08-29 user3923936

Нет, вы ошиблись. Внешняя петля - O (n), внутренняя - O (n), а самая внутренняя - O (n). Всего вы имеете O (n^3). – perreal

Этот вопрос не соответствует теме, потому что речь идет об асимптотическом анализе. – tmyklebu

@Juan, 'j' начинается с 4, но идет до' n - 1'. – perreal

Решая следующую формулу даст вам точное количество итераций (и вывести порядок сложности роста):

enter image description here

Результат эмпирически проверено!

источник

2014-08-29 08:32:56

я вижу. как насчет среднего цикла? его не суммирование? – user3923936

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

Внешний контур:

for (int j = 4; j < n; j++)

итерацию n - 4 раз, так что это O (п). Внутренний цикл:

for (int i = 0; i < j; i++)

итерации в большинстве n - 5 раз, так что это также O(n). Внутренние большинство одно:

for (int k = 0; k < n; ++k)

итерацию n раз, так что это O (п). Последняя сложность - O(n * n * n) = O(n^3).

источник

2014-08-29 08:33:29 perreal

Пойдем с количеством итераций, чтобы получить информацию о временной сложности!

Первый цикл --->

for (int j = 4; j < n; j++){...} // it will iterate for n-4 times.

Второй контур --->

for (int i = 0; i < j; i++){...} //it'll iterate for j-1 times for each iteration of outer loop started by j. See,this is dependent on First Loop(the outermost loop)...

Третий цикл --->

for (int k = 0; k < n; ++k){...} //it'll always run n times independent to any previous-iteration whenever it is executed

Таким образом, общая итерация для (в упрощенном варианте): -

(n-4)*(j-1)*n times.

Но сам j варьируется от 4 до n-1. Таким образом, j зависит от n. т.е. 4<=j<=n-1. // так, здесь J будет перебирать п-5 раз ...

Точная обработка будет своего рода это: -

n*n-5*n=n^3-5*n^2.

Оно равно O(n^3).

Таким образом, происходит в самом худшем случае анализа, число итераций будет п^3-5 * п^2 и его временная сложность будет O (N^3).

источник

2014-08-29 08:36:50

Какова наихудшая временная сложность этого алгоритма?

ответ

Смежные вопросы