Интерполяционный поиск PDF

Preview

Summary

Лабораторная работа #2 по Алгоритмам и структурам данных ...

Description

МИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра Информационной безопасности

ОТЧЕТ по лабораторной работе №1 по дисциплине «Алгоритмы и структуры данных» Тема: Интерполяционный поиск

Студент гр. Преподаватель

Воробьев Е.Г.

Санкт-Петербург 2020

Цель работы. Ознакомление с алгоритмами поиска в линейных и нелинейных структурах и оценкой эффективности алгоритмов. Основные теоретические положения. Предметы (объекты), составляющие множество, называются его элементами. Элемент множества будет называться ключом, и обозначаться латинской буквой “k” с индексом, указывающим номер элемента. Алгоритмы поиска можно разбить на следующие группы:

2

Экспериментальные результаты.

Метод Количество элементов

800

3000

7000

0.001

0.001

0.001

сортируемого массива N Время сортировки t, c Выводы. В среднем интерполяционный поиск производит O(log(log(N)) операций, в худшем случае O(N). Поиск очень похож на бинарный поиск, но есть одно отличие, вместо деления области поиска на две части интерполяционный поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента.

3

Код программы. #include #include #define MAXN 7000 using namespace std; int InterpolSearch(int *Arr, int key); int Compare(const void* x1, const void* x2); int main() { int key; int Arr[MAXN]; srand(time(0)); for (int i = 0; i < MAXN; i++) Arr[i] = rand(); qsort(Arr, MAXN, sizeof(int), Compare); for (int i = 0; i < MAXN; i++) cout...