Введение в анализ алгоритмов 0:00 Видео посвящено наилучшему, наихудшему и среднестатистическому анализу алгоритмов. Примеры: линейный поиск и бинарное дерево поиска. Будут рассмотрены временной анализ и временные зависимости.
Линейный поиск 1:04 Линейный поиск сканирует список элементов, проверяя каждый элемент по очереди. Пример: поиск седьмого элемента в списке из десяти элементов. Время поиска зависит от количества сравнений.
Наилучший и наихудший случаи линейного поиска 2:56 Наилучший случай: поиск элемента в первом индексе списка. Время: постоянное, равное единице. Наихудший случай: поиск элемента в последнем индексе списка. Время: n сравнений, что соответствует порядку n.
Среднее время линейного поиска 6:19 Среднее время: сумма всех возможных случаев, деленная на количество обращений. Пример: для n элементов среднее время равно n+1/2. Обозначения: O, Ω, Θ.
Дерево бинарного поиска 11:50 Дерево бинарного поиска организует элементы так, что меньшие элементы находятся слева от узла, а большие - справа. Пример поиска 15-го элемента: три сравнения, время равно высоте дерева log n. Наилучший случай: поиск элемента в корне, время постоянное. Наихудший случай: поиск элемента в листе, время равно n.
Наихудший вариант для бинарного дерева поиска 14:36 Наихудший вариант зависит от высоты дерева, которая равна log n. Пример: в корне 40, в левом дочернем элементе 30, и так далее. Наихудший случай - поиск элемента в листе, что занимает время, зависящее от высоты дерева.
Наилучший и наихудший случаи для бинарного дерева поиска 15:34 Наилучший случай - поиск корня, который занимает минимальное время. Наихудший случай - поиск элемента в листе, который занимает максимальное время, зависящее от высоты дерева. Высота дерева может быть минимальной log n и максимальной n.
Обозначения для анализа времени 17:20 Минимальное время наихудшего случая - log n, максимальное время - n. Время наихудшего случая зависит от высоты дерева. Обозначения для анализа: big o, omega, theta.
Заключение 18:17 Изучение наилучшего, наихудшего и среднего случаев. Использование обозначений для анализа времени. Вопросы о минимальном и максимальном времени для алгоритмов и структур данных.
