Презентация Алгоритмы обработки массивов онлайн

Содержание слайда: АЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ: ПОИСК И СОРТИРОВКА.

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

Содержание слайда: При оценке эффективности алгоритма нужно выбрать наиболее значимую операцию или группу операций. Операции сравнения. Арифметические операции.

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

Содержание слайда: Наборы данных можно разбить на 10 классов по месторасположению максимального числа: Наборы данных можно разбить на 10 классов по месторасположению максимального числа: Максимальное число на первом месте Максимальное число на втором месте Максимальное число на третьем месте …………………………………………………………………………………….. 10. Максимальное число на десятом месте Следовательно нужно оценить эффективность только 10 вариантов, а не 10!

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

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

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

Содержание слайда: 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

Содержание слайда:

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

Содержание слайда: SpSort – список элементов 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;

Содержание слайда:

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

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

Содержание слайда: Алгоритм –2. Произведем перестановку списка (без сортировки) таким образом, что элементы меньшие по величине располагаются на местах с номерами меньшими номера ключевого элемента, а элементы большие - на местах с номерами большими номера ключевого элемента. После ряда итераций в ячейке с номером «К» будет располагаться интересующий нас элемент.