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

в цикле
число циклов
Рекурсивные алгоритмы.
число операций разбиения на подзадачи
выполнение алгоритма каждой

подзадачи
объединение результатов.

группу операций.
Операции сравнения.
Арифметические операции.

данные на классы и оценить поведение алгоритма на каждом из

них.
Пример: Определить максимальное число из набора 10 чисел.
Число возможных наборов входных данных – N!.
10!= 3628800

числа:
Максимальное число на первом месте
Максимальное число на втором месте
Максимальное число

на третьем месте
……………………………………………………………………………………..
10. Максимальное число на десятом месте

Следовательно нужно оценить эффективность только 10 вариантов, а не 10!

местоположения наибольшего элемента. Наилучший случай, когда наибольший элемент находится на

первом месте, наихудший – на последнем.
Эффективность любого алгоритма проверяется исходя из анализа трёх вариантов набора начальных данных:
Наилучший случай;
Наихудший случай;
Средний случай.

Для определения максимального и минимального чисел из набора 10 чисел нужно сформировать 90 классов входных данных

по какому-либо признаку (ключу).
Элемент списка являющийся предметом поиска называется

целевым элементом.
Поиск обычно проводится не для того, чтобы убедиться в наличии того или иного элемента, а с целью получит какие-либо данные соответствующие данному ключу.

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

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

Самый простой анализ – запись порядкового номера элементов в исходном списке, соответствующих ключу.

исходного массива
j – индекс элемента массива M(j) , соответствующего ключу.

j:=1;
for i:=1 to N do
if Spisok(i)=Kluch then
begin
M(j):=i;
j:=j+1;
end

средний элемент списка и сравниваем его с ключом. Возможны три

случая:
Средний элемент списка меньше ключа;
Средний элемент списка равен ключу;
Средний элемент списка больше ключа.
В соответствии с результатом сравнения ведутся последующие действия:
Исключается из рассмотрения левая (меньше ключа) половина списка.;
Поиск завершен;
Исключается из рассмотрения правая (больше ключа) половина списка.

исходного массива
nl:=1; - левая граница списка
nr:=n; - правая граница списка
k:=0;

- признак завершения поиска
repeat
nsr := (nl+nr) div 2; - середина списка
if SpSort(nsr) < Kluch then
nl:=nsr;
else
begin
if SpSort(nsr) = Kluch then
begin
k:=1;
j:=i;
end;
else
nr:=nsr;
end;
until k<>1;

значения.
Например, выбрать запись с большим, меньшим, средним по величине

элементом или, в общем случае, с К-ым по величине элементом.

в конец списка.
В оставшейся части выбираем наибольший элемент и

помещаем его на второе место от конца списка.
Продолжаем процедуру до тех пор, пока не дойдем до К-го по величине элемента.

элементы меньшие по величине располагаются на местах с номерами меньшими

номера ключевого элемента, а элементы большие - на местах с номерами большими номера ключевого элемента.
После ряда итераций в ячейке с номером «К» будет располагаться интересующий нас элемент.