Курсовая работа: Анализ алгоритмов нечисленной обработки данных

92 – nize

srede равный 12>11 = X, следовательно искомый элемент находится выше среднего элемента.

2) 0 - verhe

5

7 - srede

11– nize

Srede равный 7< 11=X, значит нужный элемент находится ниже среднего элемента. Выполняем дальнейшее сравнение. Так как ниже остался всего один элемент, то сравниваем его с искомым.

3) 11=11

В итоге нужный элемент найден на третьем сравнении. Данный пример наглядно показывает всё удобство и легкость двоичного метода поиска. Результаты работы программы приведены в приложении Г.

2.4 Метод оценки времени поиска

Для сравнительной оценки быстроты поисков, введем условную единицу времени, равную времени, затраченному на сравнение двух элементов. Для теоретической оценки средней быстроты поиска используем формулы:

tлин = ,

где tлин – среднее время линейного поиска; (1)

N – размер массива.

tдв = log2 N,

где tдв – среднее время двоичного поиска; (2)

N – размер массива.

3 Алгоритмизация задачи

Решение задачи, поставленной в курсовом проекте, включает в себя следующие этапы:

Формирование исходного неупорядоченного массива и запись его в текстовый файл.

Линейный поиск заданного элемента в массиве.

Построение двоичного дерева.

Сортировка исходного массива деревом.

Двоичный поиск заданного элемента в отсортированном массиве.

Запись отсортированного массива в текстовый файл.

3.1 Ввод и вывод массива

Схема алгоритма создания неупорядоченного массива приведена в приложении В. Алгоритм реализован в виде процедуры Vvod (приложение Б).

Шаг 1. Если n≤16, то переход на шаг 2, иначе шаг 4.

Шаг 2 Ввод осуществляется с клавиатуры в цикле с параметром i: