Сложность вычислений | Примеры (11 кл. 136 ч.)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю)


Урок 62
§36. Сложность вычислений
(§36. Сложность вычислений)



Содержание урока

Что такое сложность вычислений?

Примеры

Что такое асимптотическая сложность?

Алгоритмы поиска

Алгоритмы сортировки

Вопросы и задания

Задачи


Примеры


Рассмотрим алгоритмы выполнения различных операций с массивом А длины n, который может быть объявлен в программе на школьном алгоритмическом языке как

целтаб А[1:n]


Пример 1. Требуется вычислить сумму первых трёх элементов массива (при n ≥ 3).

Решение этой задачи содержит всего один оператор:

Sum:=А[1]+А[2]+А[3]


Этот алгоритм включает две операции сложения и одну операцию записи значения в память, поэтому его сложность Т(n) = 3 не зависит от размера массива вообще.

Пример 2. Требуется вычислить сумму всех элементов массива. В этой задаче уже не обойтись без цикла:

Sum:=0

нц для i от 1 до n

Sum:=Sum+A[i]

кц


Здесь выполняется п операций сложения и n + 1 операций записи в память 1, поэтому его сложность Т(n) = 2n + 1 возрастает линейно с увеличением длины массива 2.


1 Здесь и далее для упрощения выводов мы не учитываем команды, необходимые для организации цикла, потому что при больших п время их выполнения очень мало в сравнении со временем выполнения остальных операторов.

2 Предполагается, что сложение любых двух чисел выполняется одинаковое время.



Пример 3. Требуется отсортировать все элементы массива по возрастанию методом выбора.

Напомним, что метод выбора предполагает поиск на каждом шаге минимального из оставшихся неупорядоченных значений (здесь i, j, nMin и с — целочисленные переменные):

нц для i от 1 до n-1

nMin:=i;

нц для j от i+1 до n

если A[j]<A[nMin] то nMin:=j все

КЦ

если nMin<>i то

c:=A[i]; A[i]:=A[nMin]; A[nMin]:=с

все

кц


Подсчитаем отдельно количество сравнений Тс(n) и количество перестановок Тр(n). Количество сравнений не зависит от данных и определяется числом шагов внутреннего цикла:

Число перестановок зависит от данных. Например, если массив уже отсортирован в нужном порядке, перестановок не будет вообще. В худшем случае на каждом шаге основного цикла происходит перестановка, всего их будет Тр(n) = n - 1.

Следующая страница Что такое асимптотическая сложность?



Cкачать материалы урока







Наверх