Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа №1.
Исследование алгоритмов поиска в массивах.
Теоретическая часть.
При решении многих задач возникает необходимость определить, содержит ли массив определенную информацию или нет. Задачи такого типа называются поиском в массиве.
Для организации поиска в массиве могут быть использованы различные алгоритмы. Наиболее простой — это алгоритм простого перебора (линейного поиска). Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены.
Для списка из n элементов лучшим случаем будет тот, при котором искомое значение равно первому элементу списка и требуется только одно сравнение. Худший случай будет тогда, когда значения в списке нет (или оно находится в самом конце списка), в случае чего необходимо n сравнений.
Если искомое значение входит в список k раз и все вхождения равновероятны, то ожидаемое число сравнений
Например, если искомое значение встречается в списке один раз, и все вхождения равновероятны, то среднее число сравнений равно . Однако, если известно, что оно встречается один раз, то достаточно n - 1 сравнений и среднее число сравнений будет равняться
(для n = 2 это число равняется 1, что соответствует одной конструкции if-then-else).
В любом случае, вычислительная сложность алгоритма O(n).
Пример реализации алгоритма линейного поиска
int LinearSearch (int *array, size_t arraySize, int key)
{
for (size_t i = 0; i < arraySize; i++)
if (array[i] == key)
return array[i];
// если ничего не нашли
return -1;
}
Общая стратегия бинарного поиска.
Если данные отсортированы по неубыванию ключа, а поиск осуществляется на отрезке [first..last] массива а, то, сравнив искомое значение х с а[mid], где mid = first + (last - first)/2, можно сделать вывод: в левой или правой части от mid находится искомое значение. С помощью одной проверки, размер области поиска уменьшается в два раза и следовательно, размер области поиска достигнет минимального значения (длина отрезка [first..last] равна 1) через шагов, где n - первоначальный размер области поиска. Сложность алгоритма составляет О(log N), где N – количество элементов в массиве.
Пример реализации алгоритма бинарного поиска
size_t first = 0;
size_t last = n;
size_t mid;
while (first < last)
{
mid = first + (last - first) / 2;
if (x <= a[mid])
last = mid;
else
first = mid + 1;
}
if (last<n && a[last] == x)
{
// Искомый элемент найден. last - искомый индекс
} else {
// Искомый элемент не найден
}
Рассмотрим скорость выполнения каждого из представленных алгоритмов для массивов размерностью от 101 до 106. Так как вычислительная сложность линейного поиска составляет O(N), то и время его выполнения будет расти как N. В случае же бинарного поиска при сложности O(log N) время выполнения будет расти логарифмически и в случае массива размерностью 106 в то время как алгоритм линейного поиска будет исполняться 106 раз, бинарный поиск потребует
log 2106=6*log210= 6*3.3213≈20
проходов цикла (выполнений алгоритма поиска).
Задание на лабораторную работу:
Изучить основные методы поиска в массивах, сравнить сложность линейного и бинарного поиска, сделать вывод о времени работы алгоритмов при размерах массива N>106. Построить UML-диаграммы составленных алгоритмов. Графически представить зависимость асимптотической сложности алгоритмов от длины массива.