Временная сложность трех вложенных циклов for

#algorithm #time-complexity #big-o #complexity-theory

#алгоритм #временная сложность #big-o #сложность -теория

Вопрос:

Существует три вложенных цикла for, и я могу найти сложность, если цикл увеличивается на 1, но если цикл увеличивается так i = c, я запутался?

     for (int i = 0; i < n; i =c)
        for (int j = 0; j < i; j  )
             for (int k=0; k < m; k  )
                 result[i,j]= x[j]-y[k]

Сложность третьего цикла for равна m, но для первого цикла for, я думаю, равно n / c, а для второго цикла for равно n ==> умножьте диапазоны вместе: n / c * n * m = n ^ 2 / c * m ==> наихудший случай — O (n ^ 2). это правильно?
Как найти общее количество итераций, используя форму суммы?

Ответ №1:

В вашем случае временная сложность зависит от двух параметров: m и n как средний цикл может быть выражен как функция первого.

Если учесть общее количество итераций, они имеют порядок:

 1/2 * m * n * (n-1) = O(mn^2)

Левая часть предполагает c=1 . Однако, учитывая c как константу, общая временная сложность не изменится.

Если c не задан как константа, результирующая временная сложность будет O(mn^2)/c

1. Я думаю, вы должны разделить это на c из-за i = c

2. Спасибо за вашу помощь. Мое замешательство было связано с частью c, и я видел здесь много примеров, если i = 2, сложность будет n / 2. c будет иметь разные значения при каждом запуске программы.

3. но если n ^ 2 является доминирующим, должен ли я включать его только в нотацию big O или должен включать все переменные O (mn ^ 2 / c) ?!

4. Зависит от того, есть ли у вас дополнительная информация m , и вы можете ее охарактеризовать. Например, если m=O(n^2) и c=O(1) тогда это становится O(n^4) , но если у вас нет никакой информации об этом, тогда вам следует уйти, так как временная сложность также зависит от этого, являясь частью ввода.

5. Большое вам спасибо за разъяснения.