Похожие презентации:
Алгоритм
1.
АлгоритмАлгоритм - это набор шагов или инструкций, предназначенных для решения
определенной задачи или выполнения конкретной операции.
2.
Алгоритмы бывают трёх типов:• Последовательный — действия выполняются по
порядку друг за другом.
• Разветвляющийся — содержит одно или несколько
логических условий и имеет несколько ветвей
обработки.
• Циклический — алгоритм, в котором действия
повторяются определенное количество.
3.
«O» большоеПонятие "O большое" помогает нам понять насколько
быстро или медленно будет работать алгоритм в
зависимости от количества входных данных.
На рисунке показаны разные временные сложности.
4.
Бинарный поиск- Это один из самых эффективных алгоритмов поиска который использует метод
решения задач “Разделяй и властвуй” (Divide and Conquer), в заранее
отсортированном массиве. У него логарифмическое время O(logn), и с
возрастанием входных данных становится только быстрее и эффективнее.
5.
"Разделяй и властвуй"- это популярный метод решения задачи,
который применяется в алгоритмах и
стратегиях решения различных задач. Этот
метод заключается в разделении сложной
задачи на более мелкие подзадачи,
решение которых проще. По окончанию
алгоритма мы соединяем все мелкие
подзадачи воедино для получения
результата.
6.
7.
Bubble sortОдин из самых простых алгоритмов сортировки
но не самых эффективных, имеет квадратичную
временную сложность O(n^2).
8.
9.
Selection sortЕще один простой метод сортировки который также
выполняется за квадратичное время.
10.
11.
Quick sortОдна из наиболее эффективных сортировок. У сортировки Хоара
линейно – логарифмическая сложность O(nlogn), которая также как и
бинарный поиск использует метод “Разделяй и властвуй”.
12.
РекурсияДанная сортировка основана на рекурсии,
то есть метод постоянно будет вызывать
самого себя пока не дойдет до
определенного результата.
13.
Для начала создадим два перегруженных метода:• Один из них публичный и принимает
в себя неотсортированный массив и
возвращает уже метод в которой мы
передаем еще и границы массива.
• Он же в свою очередь
рекурсивно вызывает самого
себя пока high больше чем low.
• В нем так же есть метод partition
в котором и происходит вся
работа
14.
partition• Приватный метод который делит массив на два под
массива на основе опорного элемента (pivot-а). То есть
все числа которые меньше опорного будут слева от него,
а числа которые больше справа соответственно.
• В самом конце возвращает опорный индекс.
15.
16.
Метод partition возвращает индекс опорного элемента что быдальнейшем понимать откуда ему начинать последующую
рекурсию.
17.
Таким образом мы можем понятьчто метод будет рекурсивно
разделяться на все более мелкие под
массивы, в конечном итоге
полностью сортировать весь массив.