Большой O для этого тройного вложенного цикла? - PullRequest
Новая
       12

Большой O для этого тройного вложенного цикла?

0 голосов
/ 31 января 2019

Что это за большая цифра? 

for (int i = 1; i < n; i++) {
    for (int j = 1; j < (i*i); j++) {
        if (j % i == 0) {
            for (int k = 0; k < j; k++) {
                // Simple computation
            }
        }
    }
}

Не могу понять это.Склонен сказать O (n ^ 4 log (n)), но чувствую, что я здесь не прав.

Ответы [ 2 ]

0 голосов
/ 31 января 2019

Это довольно запутанный анализ, поэтому давайте разберем его по частям, чтобы иметь смысл вычислений:

Самый внешний цикл выполняется для n-1 итераций (так как 1 ≤ i Следующий цикл внутри него выполняет (i² - 1) итераций для каждого индекса i внешнего цикла (так как 1 ≤ j В целом это означает, чтоколичество итераций для этих двух циклов равно сумме (i²-1) для каждого 1 ≤ i вычислению суммы первых n квадратов и является порядком величины O (n³).Примечание Оператор по модулю% требует постоянного времени (O (1)) для вычисления , поэтому проверка условия if (j % i == 0) для всех итераций этих двух циклов не повлияет на время выполнения O (n³).

Теперь поговорим о внутреннем цикле внутри условного.
Мы заинтересованы в том, чтобы узнать, сколько раз (и для каких значений j) это, если условие оценивается как истинное, поскольку это будет определять, сколько итераций будет выполняться самый внутренний цикл.Практически говоря, (j% i) никогда не будет равно 0, если j Обратите внимание, что для данного числа i (j% i == 0) тогда и только тогда, когда i является делителем числа j.Поскольку наш диапазон равен (1 ≤ j Если это сбивает с толку, рассмотрим этот пример:

Давайте предположим, что i = 4. Тогда наш индекс j будет перебирать все значения 1, .., 15 = i² и (j% i == 0) будет верно для j = 4, 8, 12 - точно (i - 1) значений.Таким образом, самый внутренний цикл будет выполнять (12 + 8 + 4 = 24) итераций.
Таким образом, для общего индекса i мы будем искать сумму: i + 2i + 3i + ... + (i-1) i, чтобы указать количество итераций, которые сделает самый внутренний цикл.

И это можно обобщить, рассчитав сумму этой арифметической прогрессии.Первое значение - это i, а последнее - (i-1) i, что приводит к сумме (i³ - i²) / 2 итераций цикла k для каждого значения i.В свою очередь, сумма этого для всех значений i может быть вычислена путем вычисления суммы кубов и суммы квадратов - для общего времени выполнения O (n⁴) итераций самого внутреннего цикла (kloop) для всех значений i.

Таким образом, в целом, время выполнения этого алгоритма будет суммой обеих сред выполнения, которые мы рассчитали выше.Мы проверили оператор if O (n³) раз, и самый внутренний цикл выполнялся для O (n⁴), поэтому, предполагая, что // Simple computation выполняется в постоянное время, наше общее время выполнения уменьшится до:

O (n³) +O (n⁴) * O (1) = O (n⁴)

0 голосов
/ 31 января 2019

Предположим, что i = 2. Тогда j может быть [1,2,3]. Цикл «k» будет выполняться только для j = 2.Аналогично для i = 3, j может быть [1,2,3,4,5,6,7,8]. Следовательно, k может работать для j = 3,6.Здесь вы можете увидеть шаблон, что для любого значения i цикл 'k' будет выполняться (i-1) раз. Длина циклов будет [i, 2 * i, 3 ​​* i, .... i *i].

Следовательно, временная сложность цикла k равна

= i + (2 * i) + (3 * i) + ..... + (i * i)

= (i ^ 2) (i + 1) / 2

Следовательно, окончательная сложность будет

= (n ^ 3)(n + 3) / 2

...