Презентация Структуры и алгоритмы обработки данных 2 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Структуры и алгоритмы обработки данных 2 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 45 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:45 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:218.50 kB
- Просмотров:73
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Структуры и алгоритмы обработки данных, 2
Лекция 2 (+3)
Сортировка
(новый раздел)
Постановка задачи
Простые алгоритмы сортировки
Сортировка выбором
Сортировка обменами
Сортировка вставками
Быстрая сортировка
Процедура разделения
Алгоритм QuickSort
Модификации
Анализ алгоритма
№2 слайд
Содержание слайда: Сортировка 2
Дан массив a: array [1..n] of Ordinal
Отрезок (сегмент) массива a[p..q] упорядочен:
Sort (a, p, q) ( i: p i q: a[i] a[i+1])
Предусловие: a[1..n] = a0[1..n]
Постусловие: Sort (a, 1, n) & & Перестановка(a[1..n], a0[1..n]),
где Перестановка(a[1..n], a0[1..n])
( i: 1 i n: (N j: 1 j n: a[ i ] = a0[ j ] ) =
= (N j: 1 j n: a[ i ] = a [ j ] ) )
№3 слайд
Содержание слайда: Сортировка 3
Простые алгоритмы сортировки
Сортировка выбором
Идея. Пример.
Список (удаление и вставка)
№4 слайд
Содержание слайда: Сортировка 4
№5 слайд
Содержание слайда: Сортировка 5
Простые алгоритмы сортировки
Сортировка выбором
Инвариант внешнего цикла:
№6 слайд
Содержание слайда: Сортировка 6
Сортировка 6
№7 слайд
Содержание слайда: Сортировка 7
Анализ сортировки выбором
Сi – число сравнений при выборе минимального элемента на i-ом шаге
(в сегменте из (n – i + 1) элементов)
Сi = n – i
Суммарно по всем шагам:
№8 слайд
Содержание слайда: Сортировка 8
Анализ сортировки выбором
Пусть Mi – число перестановок на i-ом шаге,
включая обновления текущего минимума
(в сегменте из (n – i + 1) элементов).
В худшем случае
(обратно упорядоченный массив):
Mi =(n – i) + 3
Тогда суммарно по всем шагам (i1..n1):
Mmax= (n2 – n)/2 + 3(n – 1)
№9 слайд
Содержание слайда: Сортировка 9
Анализ сортировки выбором
В среднем:
Вероятность того, что произойдет обновление
текущего минимума
на j-ом шаге внутреннего цикла = 1/j
(любой, в том числе последний из j элементов - минимальный).
Т.о. за i-й шаг среднее (М.О.) число перестановок
= 1/2 + 1/3 + 1/4 +… + 1/(n-i+1) = Hn-i+1 -1,
где частичная сумма гармонического ряда
Hk= 1 + 1/2 + 1/3 + … + 1/k,
Hk= ln k + + 1/(2k) +... , где - постоянная Эйлера.
Итак, за i-й шаг внешнего цикла среднее число присваиваний Hn-i+1 -1+3= Hn-i+1 +2 ln (n-i+1) + +2
№10 слайд
Содержание слайда:
№11 слайд
Содержание слайда: Сортировка 11
Простые алгоритмы сортировки
Сортировка обменами («пузырьковая»)
№12 слайд
Содержание слайда: Сортировка 12
№13 слайд
Содержание слайда: Сортировка 13
№14 слайд
Содержание слайда: Сортировка 14
Простые алгоритмы сортировки
Сортировка обменами
Инвариант внешнего цикла
For i:=n downto 2 do
№15 слайд
Содержание слайда: Сортировка 15
Сортировка обменами (пузырьковая)
for i:=n downto 2 do
begin
{просмотр a[1..i] с обменами соседних элементов}
for j := 2 to i do
if a[j1] > a[j] then a[j1] a[j] ;
{a[i] = max a[1..i] }
end
№16 слайд
Содержание слайда: Анализ сортировки обменами (пузырьковой)
Анализ сортировки обменами (пузырьковой)
№17 слайд
Содержание слайда: Сортировка 17
Простые алгоритмы сортировки
Сортировка вставками (включением)
№18 слайд
Содержание слайда: Сортировка 18
Простые алгоритмы сортировки
Сортировка ВСТАВКАМИ
Инвариант внешнего цикла:
№19 слайд
Содержание слайда: Сортировка прямыми ВСТАВКАМИ
Сортировка прямыми ВСТАВКАМИ
№20 слайд
Содержание слайда: Сортировка 20
Простые алгоритмы сортировки
Сортировка ВСТАВКАМИ
АЛГОРИТМ Прямые вставки (StraightInsertion)
type index=0..nMax;
index1=1..nMax;
index2=0..nMax+1;
mass=array [index] of Integer;
№21 слайд
Содержание слайда: Сортировка 21
procedure StraightInsertion ( var a: mass; n: index1; k: index1 );
{ сортировка массива методом вставки }
var i: index;
j: index1;
x: Integer;
begin
for i:=2 to n do
begin { включить a[i] на соотв. место в a[1..i] }
x := a[i]; a[0] := x; { a[0] - "барьер" }
j := i;
while x < a[j-1] do
begin { 1<=j<=i }
a[j] := a[j-1];
j := j-1
end { while };
a[j] := x
end { for }
end { StraightInsertion };
№22 слайд
Содержание слайда: Сортировка 22
Сортировка ПРЯМЫМИ ВСТАВКАМИ
Анализ
Число сравнений число перемещений.
Число сравнений на i –ом шаге Ci = i/2 в среднем.
Тогда по всем шагам i2..n
№23 слайд
Содержание слайда: Сортировка БИНАРНЫМИ ВСТАВКАМИ
Сортировка БИНАРНЫМИ ВСТАВКАМИ
for i:=2 to n do
begin
{ Найти место a[i] среди a[1..i-1] }
x := a[i]; L:=1; R:=i;
while LR do
begin
m:=(L+R) div 2;
if a[m] < x then L:=m+1 else R:=m
end; {(L1..i) & (a[L-1] < x a[L])}
{сдвинуть a[L..i-1] на позицию вправо на место a[L+1..i]}
for j:=i downto L+1 do a[j] := a[j-1];
{вставить x на место a[L]}
a[L]:=x
end {for}
№24 слайд
Содержание слайда: Сортировка БИНАРНЫМИ ВСТАВКАМИ Анализ алгоритма
Сортировка БИНАРНЫМИ ВСТАВКАМИ Анализ алгоритма
Число сравнений на i –ом шаге Ci log2i.
По всем шагам (i2..n)
№25 слайд
Содержание слайда: Сортировка 25
Быстрая сортировка (QuickSort)
№26 слайд
Содержание слайда: Сортировка 26
Быстрая сортировка (QuickSort)
№27 слайд
Содержание слайда: while q<= p do
while q<= p do
begin
if a[q] <= x then q := q+1
else
if a[p] > x then p := p-1
else { a[p]<= x < a[q] }
begin
y := a[p];
a[p] := a[q];
a[q] := y;
q := q+1;
p := p-1
end { if };
end { while };
a[m] := a[p];
a[p] := x;
end { Partition1 };
№28 слайд
Содержание слайда: Быстрая сортировка:
Быстрая сортировка:
разделение и слияние
№29 слайд
Содержание слайда: Сортировка 29
procedure Sortp1 (var a: mass; m, n: index1; k: index1 );
var p, q: index2;
begin
Partition1 ( a, m, n, p );
if p-m>k then Sortp1 ( a, m, p-1, k );
q:=p+1;
if n-q+1>k then Sortp1 ( a, q, n, k )
{ подмассив длиной <= k не сортируем !
1<=k<=50 , при k=1 - полная сортировка }
end { Sortp1 };
№30 слайд
Содержание слайда: Сортировка 30
begin { QuickSort1 }
Sortp1( a, 1, n, k );
if k>1 then { окончательная сортировка
простым методом }
StraightInsertion ( a, n ,1)
end { QuickSort1 };
№31 слайд
Содержание слайда: Быстрая сортировка
Быстрая сортировка
Неполная сортировка. Выбор k
№32 слайд
Содержание слайда: Первый вызов Partition 32
1 2 3 4 5 6 7 8 9 10 11 12 13 14
у п О р я д о ч И в а н и е
о п О р я д у ч И в а н и е
о е О р я д у ч И в а н и п
о е О р я д у ч И в а н и п
о е О и я д у ч И в а н р п
о е О и н д у ч И в а я р п
о е О и н д у ч И в а я р п
о е О и н д а ч И в у я р п
о е О и н д а в И ч у я р п
И е О и н д а в о ч у я р п
№33 слайд
Содержание слайда: Сортировка 33
1 2 3 4 5 6 7 8 9 10 11 12 13 14
И е О и н д а в о ч у я р п
№34 слайд
Содержание слайда: Сортировка 34
Анализ. Лучший случай
№35 слайд
Содержание слайда: Сортировка 35
Анализ. Худший случай
№36 слайд
Содержание слайда:
№37 слайд
Содержание слайда: Анализ. В среднем
Анализ. В среднем
№38 слайд
Содержание слайда: Анализ. В среднем (продолжение)
Анализ. В среднем (продолжение)
№39 слайд
Содержание слайда: Анализ. В среднем (продолжение)
Анализ. В среднем (продолжение)
№40 слайд
Содержание слайда: Приложение Асимптотические оценки
Обозначения О(f(n)), (f(n)), (f(n))
Для указания множества функций,
которые не более чем в постоянное число раз превосходят f (n) при достаточно большом n,
используется обозначение О(f(n)).
Запись g (n) О(f(n)) означает, что
cуществуют:
вещественная константа C > 0 и
натуральная константа n0 ,
для которых g (n) C f (n) при всех n n0
№41 слайд
Содержание слайда: Асимптотические оценки
Обозначение О(f(n))
№42 слайд
Содержание слайда: Асимптотические оценки
Обозначения О(f(n)), (f(n)), (f(n))
Для указания множества функций,
которые не менее чем в постоянное число раз превосходят f (n) при достаточно большом n, используется обозначение (f(n)).
Запись g (n) (f(n)) означает, что
существуют :
вещественная константа C > 0 и
натуральная константа n0 ,
для которых g (n) C f (n) при всех n n0.
№43 слайд
Содержание слайда: Асимптотические оценки
Обозначение (f(n))
№44 слайд
Содержание слайда: Асимптотические оценки
Обозначения О(f(n)), (f(n)), (f(n))
Для указания множества функций того же порядка, что и f (n) при достаточно большом n, используется обозначение (f(n))
Запись g (n) (f(n)) означает, что
существуют :
вещественные константы C1 > 0 и C2 > 0 и
натуральная константа n0 , для которых
C1 f (n) g (n) C2 f (n) при всех n n0
№45 слайд
Содержание слайда: Асимптотические оценки
Обозначение (f(n))
Скачать все slide презентации Структуры и алгоритмы обработки данных 2 одним архивом:
