Int _tmain(int argc, _tchar* argv[])

{ setlocale(LC_ALL, "rus");

int m = 4;

AAA a1(1,"Вася"), a2(2,"Петя");

AAA a3(3,"Коля"), a4 (1,"Вова");

PrHash H = Create(m, hf);

H.Insert(&a1); H.Insert(&a2);

H.Insert(&a3); H.Insert(&a4);

H.Scan();

cout<<endl;

cout<<"Найден элемент = ";

AAA_print(H.Search(&a2));

cout<<endl;

H.Delete(&a3);

cout<<endl;

H.Scan();

}

Исследование времени

Хэш-таблица с прямой адресацией - совокупность связанных списков. По мере того, как таблица растет, увеличивается количество списков и, соответственно, среднее число узлов в каждом списке уменьшается.

Если количество элементов равно n, а размер таблицы – m = 1 (hashTableSize = 1), то таблица вырождается в один список длиной n.

Если размер таблицы m = 2, то получается два списка по n/m элементов в каждом.

Установлено, что для эффективного хэширования коэффициент заполнения должен быть в пределах от 0,2 до 0,7.

В таблице приведена зависимость времени поиска от размера таблицы.

Алгоритм Search(T, key) (считаем, что хэш-функция имеет вид  H(key,j)).

1.     Вычисляется:  H(key,0), адрес  строки хэш-таблицы.

2.     Если s -> key = key, то s указывает на искомый элемент.

3.     Если s -> key = NIL, то искомого элемента нет. 

4.     Если s -> key ≠ key, то  повторяем вычисление s = H(key, j), j = 1, 2… и переходим на п.2.

Оценка сложности алгоритмов

Процесс создания компьютерной программы состоит из нескольких этапов:

• Формализация и разработка технического задания.

• Разработка алгоритма решения задач.

• Написание, тестирование, отладка и документирование программы.

• Получение решения.

Выбор подходящего алгоритма или его разработка часто вызывает определенные трудности. Иногда необходимо, чтобы алгоритм отвечал противоречивым требованиям: минимальное время выполнения, минимум объема памяти и т.п.

Теория алгоритмов — наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления.

К задачам теории алгоритмов относятся формальное доказательство алгоритм. неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п.

В настоящее время теория алгоритмов развивается, главным образом, по трем направлениям:

• классическая теория алгоритмов изучает проблемы формулировки задач, проводит классификацию задач по классам сложности и др.;

• теория асимптотического анализа алгоритмов рассматривает методы получения асимптотических оценок ресурсоемкости или времени выполнения алгоритмов;

• теория практического анализа алгоритмов решает задачи получения явных функций трудоёмкости, поиска критериев качества алгоритмов, разработки методики выбора рациональных алгоритмов и пр.

На время выполнения программы влияют различные факторы:

• ввод исходных данных;

• качество кода программы;

• скорость выполнения машинных инструкций;

• сложность алгоритма и пр.

Поскольку время выполнения программы во многом определяется количеством данных, то его можно определить как функцию от данных – T(n).

Параметр n может быть количеством обрабатываемого набора данных, количеством символов в строке, размером файла с данными, степенью полинома и т.п.