Я работаю над курсом структуры данных, и я не уверен, как продолжить этот анализ Big O:
sum = 0;
for(i = 1; i < n; i++)
for(j = 1; j < i*i; j++)
if(j % i == 0)
for(k = 0; k < j; k++)
sum++;
Моя первоначальная идея состоит в том, что после редукции это O (n ^ 3), потому что самый внутренний цикл будет выполняться только тогда, когда j/i не имеет остатка, и правило умножения неприменимо. Правильно ли здесь мои рассуждения?
Пусть здесь игнорируется внешний цикл для второго, и проанализируем его в терминах i.
Средний цикл запускает i^2 раз и вызывает внутренний цикл всякий раз, когда j%i == 0, что означает, что вы запускаете его на i, 2i, 3i, ...,i^2, и каждый раз, когда вы запускаете до соответствующего j, это означает, что суммарное время выполнения внутренней петли:
i + 2i + 3i + ... + (i-1)*i = i(1 + 2 + ... + i-1) = i* [i*(i-1)/2]
Последнее равенство получается из суммы арифметической прогрессии.
Вышеуказанное находится в O(i^3).
повторите это во внешнем цикле, который работает от 1 до n, и вы получите время работы O(n^4), поскольку у вас на самом деле есть:
C*1^3 + C*2^3 + ... + C*(n-1)^3 = C*(1^3 + 2^3 + ... + (n-1)^3) =
= C/4 * (n^4 - 2n^3 + n^2)
Последнее уравнение получается из суммы кубов
И выше в O(n^4), что является вашей сложностью.