Понятие о сложности алгоритмов (Python)

Пример. Проведите анализ трудоёмкости задачи на суммирование элементов квадратной матрицы.

Программный код:

sum = 0

for i in range (N):

	for j in range (M):

		sum = sum + a [i][j]

Применение методики анализа конструкции «Цикл» даёт количество операций:

• во внутреннем цикле f₁ (n) = 1 + 3n + 4n;
• во внешнем цикле f₂ (n) = 1 + 3n + n ⋅ f₁ (n);
• итогово F (n) = 1 + 1 + 3n + n ⋅ (1 + 3n + 4n) = 2 + 4n + 7n² = Θ (n²).