🗊Презентация Оценка сложности алгоритмов

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Оценка сложности алгоритмов, слайд №1Оценка сложности алгоритмов, слайд №2Оценка сложности алгоритмов, слайд №3Оценка сложности алгоритмов, слайд №4Оценка сложности алгоритмов, слайд №5Оценка сложности алгоритмов, слайд №6Оценка сложности алгоритмов, слайд №7Оценка сложности алгоритмов, слайд №8Оценка сложности алгоритмов, слайд №9Оценка сложности алгоритмов, слайд №10Оценка сложности алгоритмов, слайд №11Оценка сложности алгоритмов, слайд №12Оценка сложности алгоритмов, слайд №13Оценка сложности алгоритмов, слайд №14Оценка сложности алгоритмов, слайд №15
Скачать
Вы можете ознакомиться и скачать презентацию на тему Оценка сложности алгоритмов. Доклад-сообщение содержит 15 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


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

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


Оценка сложности алгоритмов, слайд №7
Описание слайда:

Слайд 8


Количество шагов n (сложность алгоритма) и размер массива N связаны формулой: Количество шагов n (сложность алгоритма) и размер массива N связаны формулой: 2n=N T(N)=log2N
Описание слайда:
Количество шагов 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
Описание слайда:
Ход сортировки 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
Описание слайда:
Ход сортировки 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 проход по массиву – упорядочим весь массив.
Описание слайда:
Ход сортировки 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;
Описание слайда:
Программа Один проход по массиву: 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;
Описание слайда:
Программа Этот проход надо повторить 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с)
Описание слайда:
Сложность алгоритма Алгоритм делает порядка (N-1)+(N-2)+…+2+1=N(N-1)/2 шагов, что примерно равно N2. T(N)= N2 При N=1000000 элементов потребуется примерно 10000002=1012 шагов (103с)

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию