Оценка сложности алгоритмов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Оценка сложности алгоритмов. Доклад-сообщение содержит 15 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Оценка сложности алгоритмов На примере обработки массивов

Слайд 2

Описание слайда:

Алгоритм нахождения наибольшего элемента в массиве

Слайд 3

Описание слайда:

Алгоритм поиска элемента в массиве размерности N Mas:array[1..N] of integer; А- некоторое искомое значение Идея алгоритма: нужно двигаться по массиву и сравнивать каждую ячейку с заданным значением. Как только будет обнаружено равенство либо достигнут конец массива, то необходимо остановиться и выдать сообщение.

Слайд 4

Описание слайда:

Алгоритм поиска элемента в массиве размерности N

Слайд 5

Описание слайда:

Алгоритм поиска в упорядоченном массиве размерности N Идея алгоритма: остановиться на первом элементе, большем того, который ищем, т.е. в условии заменить Mas [i]

Слайд 6

Описание слайда:

Алгоритм поиска в упорядоченном массиве размерности N Идея алгоритма: 1. Возьмём элемент, стоящий в середине массива. Если он равен А, то алгоритм закончен. Если элемент > А, то искомый элемент находится в левой половине массива, а правую половину можно больше не рассматривать. 2. Аналогично, если элемент

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Количество шагов n (сложность алгоритма) и размер массива N связаны формулой: Количество шагов n (сложность алгоритма) и размер массива N связаны формулой: 2n=N T(N)=log2N

Слайд 9

Описание слайда:

Задача: упорядочить массив (другим массивом пользоваться нельзя) Способ решения: «пузырьковая сортировка»

Слайд 10

Описание слайда:

Ход сортировки 1.) исходный массив 3 7 9 4 1 5 2 8 не меняем местами 2 и 8 3 7 9 4 1 5 2 8 меняем местами 5 и 2 3 7 9 4 1 2 5 8 не меняем 1 и 2 3 7 9 4 1 2 5 8 меняем местами 4 и 1 3 7 9 1 4 2 5 8 меняем местами 9 и 1 3 7 1 9 4 2 5 8 меняем местами 7 и 1 3 1 7 9 4 2 5 8 меняем местами 3 и 1 1 3 7 9 4 2 5 8

Слайд 11

Описание слайда:

Ход сортировки 2.) Повторяем проход с конца массива, но теперь не доходя до первого элемента. 1 3 7 9 4 2 5 8 не меняем местами 5 и 8 1 3 7 9 4 2 5 8 не меняем местами 5 и 2 1 3 7 9 4 2 5 8 не меняем 4 и 2 1 3 7 9 2 4 5 8 меняем местами 2 и 9 1 3 7 2 9 4 5 8 меняем местами 2 и 7 1 3 2 7 9 4 5 8 меняем местами 2 и 3 1 2 3 7 9 4 5 8

Слайд 12

Описание слайда:

Ход сортировки 3.) Сделав N-1 проход по массиву – упорядочим весь массив.

Слайд 13

Описание слайда:

Программа Один проход по массиву: For j:=N downto 2 do if Mas[j-1]>Mas[j] then begin Tmp:=Mas[j]; Mas[j]:=Mas[j-1]; Mas[j-1]:=Tmp End;

Слайд 14

Описание слайда:

Программа Этот проход надо повторить N-1 раз. For i:=2 to N do For j:=N downto i do if Mas[j-1]>Mas[j] then begin Tmp:=Mas[j]; Mas[j]:=Mas[j-1]; Mas[j-1]:=Tmp End;

Слайд 15

Описание слайда:

Сложность алгоритма Алгоритм делает порядка (N-1)+(N-2)+…+2+1=N(N-1)/2 шагов, что примерно равно N2. T(N)= N2 При N=1000000 элементов потребуется примерно 10000002=1012 шагов (103с)