Логотип
Войти
Информатика • 8 класс
100

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

  • Элементарные операции:
    • простое присваивание;
    • одномерная индексация a[i];
    • арифметические операции: (*, /, , +);
    • операции сравнения;
    • логические операции (OR, AND, NOT).
  • Пример. Проведём анализ трудоемкости задачи на суммирование элементов квадратной матрицы.
  • Применение методики анализа конструкции «Цикл» даёт:
    • внутренний f1(n) = 1 + 3n + 4n;
    • внешний f2(n) = 1 + 3n + nf1(n);
    • окончательно F(n) = 1 + 1 + 3n + n ⋅ (1 + 3n + 4n) = = 2 + 4n + 7n2 = Θ (n2).
  • Программный код:

sum := 0;

for i := 1 to N do begin

for j := 1 to M do begin

sum := sum + a[i,j]

end

end

Было полезно?

Рекомендуем

Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках
Зарегистрироваться в «Облаке знаний»