Анализ простейших алгоритмов (Паскаль)

• Элементарные операции:

  • простое присваивание;
  • одномерная индексация a[i];
  • арифметические операции: (*, /, ‒, +);
  • операции сравнения;
  • логические операции (OR, AND, NOT).
• Пример. Проведём анализ трудоемкости задачи на суммирование элементов квадратной матрицы.
• Применение методики анализа конструкции «Цикл» даёт:

  • внутренний 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²).
• Программный код:

sum := 0;

for i := 1 to N do begin

for j := 1 to M do begin

sum := sum + a[i,j]

end

end