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

Сентябрь 2, 2022

Главная
Алгебра
Алгоритмы обработки массивов

Содержание

2. Эффективность алгоритма Алгоритмы можно разделить на два класса: Алгоритмы с повторением. число операций в цикле число
3. При оценке эффективности алгоритма нужно выбрать наиболее значимую операцию или группу операций. Операции сравнения. Арифметические операции.
4. Классы входных данных При оценке эффективности алгоритма нужно попытаться разбить входные данные на классы и оценить
5. Наборы данных можно разбить на 10 классов по месторасположению максимального числа: Максимальное число на первом месте
6. Варианты отличаются друг от друга числом перестановок в зависимости от местоположения наибольшего элемента. Наилучший случай, когда
7. Списки данных могут быть двух типов – отсортированными или неотсортированными по какому-либо признаку (ключу). Элемент списка
8. Последовательный поиск. Поиск проводится в неотсортированном списке. Последовательно просматривается список элементов, начиная с первого. Элементов списка,
9. Spisok – список элементов Kluch - целевой элемент i – индекс элемента исходного массива j –
10. Конец цикла a m m[j]=i a[i]=ключ да нет j
11. Двоичный поиск. Поиск проводится в отсортированном списке. Алгоритм поиска : Выбираем средний элемент списка и сравниваем
12. SpSort – список элементов Kluch - целевой элемент i – индекс элемента исходного массива nl:=1; -
13. nl nsr nr nl nsr nl nr nsr nr nl nsr nr nl nsr nr
14. Выборка. Задача - выбрать из списка элемент, не имеющий какого-либо конкретного значения. Например, выбрать запись с
15. Алгоритм –1. Выбираем из списка наибольший элемент и помещаем его в конец списка. В оставшейся части
17. Скачать презентацию

Слайд 2

Эффективность алгоритма
Алгоритмы можно разделить на два класса:
Алгоритмы с повторением.
число операций в

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

Слайд 3

При оценке эффективности алгоритма нужно выбрать наиболее значимую операцию или группу

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

Слайд 4

Классы входных данных
При оценке эффективности алгоритма нужно попытаться разбить входные данные

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

Слайд 5

Наборы данных можно разбить на 10 классов по месторасположению максимального числа:
Максимальное

число на первом месте
Максимальное число на втором месте
Максимальное число на третьем месте
……………………………………………………………………………………..
10. Максимальное число на десятом месте
Следовательно нужно оценить эффективность только 10 вариантов, а не 10!

Слайд 6

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

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

Слайд 7

Списки данных могут быть двух типов – отсортированными или неотсортированными по

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

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

Слайд 8

Последовательный поиск.
Поиск проводится в неотсортированном списке.
Последовательно просматривается список элементов, начиная

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

Слайд 9

Spisok – список элементов
Kluch - целевой элемент
i – индекс элемента исходного

массива
j – индекс элемента массива M(j) , соответствующего ключу.
j:=1;
for i:=1 to N do
if Spisok(i)=Kluch then
begin
M(j):=i;
j:=j+1;
end

Слайд 10

Конец цикла
a
m
m[j]=i
a[i]=ключ
да
нет
j

Слайд 11

Двоичный поиск.
Поиск проводится в отсортированном списке. Алгоритм поиска :
Выбираем средний

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

Слайд 12

SpSort – список элементов
Kluch - целевой элемент
i – индекс элемента исходного

массива
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;

Слайд 13

nl
nsr
nr
nl
nsr
nl
nr
nsr
nr
nl
nsr
nr
nl
nsr
nr

Слайд 14

Выборка.
Задача - выбрать из списка элемент, не имеющий какого-либо конкретного значения.

Например, выбрать запись с большим, меньшим, средним по величине элементом или, в общем случае, с К-ым по величине элементом.

Слайд 15

Алгоритм –1.
Выбираем из списка наибольший элемент и помещаем его в

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

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

Содержание

Эффективность алгоритмаАлгоритмы можно разделить на два класса:Алгоритмы с повторением.число операций в

При оценке эффективности алгоритма нужно выбрать наиболее значимую операцию или группу

Классы входных данныхПри оценке эффективности алгоритма нужно попытаться разбить входные данные

Наборы данных можно разбить на 10 классов по месторасположению максимального числа:Максимальное

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

Списки данных могут быть двух типов – отсортированными или неотсортированными по

Последовательный поиск.Поиск проводится в неотсортированном списке. Последовательно просматривается список элементов, начиная

Spisok – список элементовKluch - целевой элементi – индекс элемента исходного

Конец циклаamm[j]=ia[i]=ключданетj

Двоичный поиск.Поиск проводится в отсортированном списке. Алгоритм поиска : Выбираем средний

SpSort – список элементовKluch - целевой элементi – индекс элемента исходного

nlnsrnrnlnsrnlnrnsrnrnlnsrnrnlnsrnr

Выборка.Задача - выбрать из списка элемент, не имеющий какого-либо конкретного значения.

Алгоритм –1. Выбираем из списка наибольший элемент и помещаем его в

Похожие презентации