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

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

Элементарные операции:
- простое присваивание;
- одномерная индексация a [i];
- арифметические операции (*, /, –, +, %);
- операции сравнения;
- логические операции (||, &&, !, ^).
Пример. Проведите анализ трудоёмкости задачи на суммирование элементов квадратной матрицы.

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

sum = 0;
for (int i = 0; i < N; i++)
    { for (int j = 0; j < M; j++)
        {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²).

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

Рекомендуем

Вы учитель или ученик?

Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ

Учителю

Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников

Ученику

Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках