Презентация Оценка сложности алгоритмов онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Оценка сложности алгоритмов абсолютно бесплатно. Урок-презентация на эту тему содержит всего 15 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:15 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:196.00 kB
- Просмотров:64
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Оценка сложности алгоритмов
На примере обработки массивов
№2 слайд
Содержание слайда: Алгоритм нахождения наибольшего элемента в массиве
№3 слайд
Содержание слайда: Алгоритм поиска элемента в массиве размерности N
Mas:array[1..N] of integer;
А- некоторое искомое значение
Идея алгоритма: нужно двигаться по массиву и сравнивать каждую ячейку с заданным значением. Как только будет обнаружено равенство либо достигнут конец массива, то необходимо остановиться и выдать сообщение.
№4 слайд
Содержание слайда: Алгоритм поиска элемента в массиве размерности N
№5 слайд
Содержание слайда: Алгоритм поиска в упорядоченном массиве размерности N
Идея алгоритма: остановиться на первом элементе, большем того, который ищем, т.е. в условии заменить
Mas [i] <A
№6 слайд
Содержание слайда: Алгоритм поиска в упорядоченном массиве размерности N
Идея алгоритма: 1. Возьмём элемент, стоящий в середине массива. Если он равен А, то алгоритм закончен. Если элемент > А, то искомый элемент находится в левой половине массива, а правую половину можно больше не рассматривать.
2. Аналогично, если элемент <А, то искомый элемент в правой половине.
3. С оставшейся частью массива выполняем аналогичные действия.
4. Эти действия повторяем пока нужный элемент не будет найден или в массиве не останется элементов.
№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с)
Скачать все slide презентации Оценка сложности алгоритмов одним архивом:
