Анализ алгоритмов на сложность времени

Question

Я анализирую алгоритм и просто хочу знать, нахожусь ли я на правильном пути.

Для этого алгоритма я рассчитываю только умножения в строке с *** в них.

Вот алгоритм:

1. Итак, я начинаю с самой внутренней строки, я вижу, что там есть 2 операции (два умножения).
2. Теперь я смотрю на 2 внутренних цикла, поэтому я могу сказать,что p=p*20*z исполняется ровно (j) + (j-1)+(j-2)+(j-3)...1 раз.Это оказывается равным j(j+1)/2.
3. Таким образом, всего, так как существует два умножения, это происходит 2 * (j(j+1)/2).
4. Затем, наконец, цикл «i» происходит ровно n раз, так что в целом это n(2 * (n(n+1)/2)).

Это мой мыслительный процесс, стоящий за этим.Я прав?Спасибо.

Answer 1

Ваш мыслительный процесс правильный. Вам нужно заменить термин j на n (n - наибольшее значение, которое может принять j), но это, вероятно, опечатка.

Кроме того, вы можете упростить дальше, где вы находитесь:

n(2*(n(n+1)/2))
2*n*(n^2+n)/2
n^3+n^2

=> O(n^3)

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

Answer 2

Вычисление в этом конкретном примере может быть упрощено, если вы обнаружите, что все три цикла имеют одинаковое условие выхода up to n:

1. i <= n
2. j <= n
3. k <= j

По сути, третий цикл будет также выполнять n итераций, потому что j <= n так k <= n, это означает, что сложность будет n * n * n = O(n ^ 3)

Answer 3

Вот как можно методично получить порядок роста вашего алгоритма: