Информатика • 8 класс

Сложность вычислений (Паскаль)

Элементарные операции:
- простое присваивание;
- одномерная индексация a [i];
- арифметические операции (*, /, –, +);
- операции сравнения;
- логические операции (OR, AND, NOT).
Пример. Проведите анализ трудоёмкости задачи на суммирование элементов квадратной матрицы.
Программный код:
sum := 0;
for i := 1 to N do Begin
for j := 1 to M do begin
sum := sum + a [i, j]
end
End.
Применение методики анализа конструкции «Цикл» даёт количество операций:
- во внутреннем цикле 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²).