Алгоритмическая сложность. Оценка роста функции. Оценка сверху, снизу, в среднем.
Алгоритмическая (Вычислительная) сложность – это параметр для сравнивнения быстродействия алгоритмов, чётко описывающее их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входных данных.
Временная сложность алгоритма — это функция от размера входных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.
Оценка
роста функции (оценка слоности) – это
оценка алгоритма (по времени выполнения
или по памяти) некоторой функцией от
(количество входной информации),
характеризующего изменение времени
работы алгоритма с увеличением параметра
.
Оценка сверху – это оценка работы алгоритма в худшем случаи. Например для сортировки – обратно сортированная последовательность.
Оценка снизу – это оценка работы алгоритма в лучшем случаи. Например для сортировки – уже отсортированная последовательность.
Оценка в среднем – это оценка работы алгоритма в среднем случаи. Например для сортировки – частично отсортированная последовательность.
Алгоритмы поиска. Линейный поиск.
Алгоритм поиска – последовательность операций сравнения, с искомым экземпляром данных, где очередные элементы в структура данных (где выполяется поиск) выбираюстя исходя от алгоритма поиска. Если после завершения алгоритма искомым экземпляром данных не был обнаружен в структуре данных, алгоритм завершает работу.
Линейный, последовательный поиск — алгоритм нахождения заданного значения в произвольной структуре данных. Данный алгоритм является простейшим алгоритмом поиска и работает за линейное время – с увеличением данных время выполнения увеличивается прямо-пропорционально. ''Метод поиска в лоб'' – перебирать все элементы в структуре данных начиная с первого (или с последнего) элемента и сравнить с искомым значением.
Псевдо код:
ЦИКЛ пока не закончились элементы, для каждого элемента
ЕСЛИ очередной элемент совпадает с искомым, ТО
нашли, выходим из цикла
Конец ЕСЛИ
Конец ЦИКЛА
Алгоритмы поиска. Бинарный поиск.
Алгоритм поиска – последовательность операций сравнения, с искомым экземпляром данных, где очередные элементы в структура данных (где выполяется поиск) выбираюстя исходя от алгоритма поиска. Если после завершения алгоритма искомым экземпляром данных не был обнаружен в структуре данных, алгоритм завершает работу.
Двоичный (бинарный) поиск – классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. В каждой итерации работы алгоритма в массиве данных выбирается средний элемент и сравнивается с искомым элементом, исходя из того будет элемент болше или меньше искомого, поиск продолжается в соответствующей половине.
Псевдокод:
Пусть есть некий отсортированный массив. Рекурсивно выполнить.
ФУНКЦИЯ ПОИСКА (МАССИВ, НАЧАЛО, КОНЕЦ)
вычислить СРЕДНИЙ элемент, // средний = (int)(НАЧАЛО+КОНЕЦ / 2)
сравнить с искомым
ЕСЛИ ИСКОМЫЙ < СРДНЕГО
ФУНКЦИЯ ПОИСКА (МАССИВ, НАЧАЛО, СРЕДНИЙ)
Конец ЕСЛИ
ЕСЛИ ИСКОМЫЙ > СРДНЕГО
ФУНКЦИЯ ПОИСКА (МАССИВ, СРЕДНИЙ, КОНЕЦ)
Конец ЕСЛИ
ИНАЧЕ
нашли
Конец ИНАЧЕ
Конец ФУНКЦИИ