Лабораторная работа №5 «Сравнительный анализ алгоритмов поиска» Выполнил студент группы 8В83

Научно-исследовательский университет

Томский политехнический университет

Институт Кибернетики

Кафедра ОСУ

Структуры и алгоритмы обработки данных



ЛАБОРАТОРНАЯ РАБОТА № 5

«Сравнительный анализ алгоритмов поиска »

Выполнил студент группы 8В83		А.Н.Ролдугин
Проверил асс. каф. ОСУ		А.В. Черний

Цель работы
Изучение алгоритмов поиска элемента в массиве и закрепление навыков в проведении сравнительного анализа алгоритмов.

Задание (15):
1. Изучить алгоритмы поиска:

1) в неупорядоченном массиве:

а) линейный;

б) быстрый линейный;

2) в упорядоченном массиве:

а) быстрый линейный;

б) бинарный;

2. Разработать и программно реализовать средство для проведения экспериментов по определению временных характеристик алгоритмов поиска.

3. Провести эксперименты по определению временных характеристик алгоритмов поиска. Результаты экспериментов представить в виде таблиц 4.1 и 4.2. Клетки таблицы 4.1 содержат максимальное количество операций сравнения при выполнении алгоритма поиска, а клетки таблицы 4.2 – среднее число операций сравнения.

4. Построить графики зависимости количества операций сравнения от количества элементов в массиве.

5. Определить аналитическое выражение функции зависимости количества операций сравнения от количества элементов в массиве.

6. Определить порядок функций временной сложности алгоритмов поиска.


Листинг алгоритма(Java)

/*LS()-линейный поиск

QLS()-быстрый линейный поиск

QLSL()-быстрый линейный поиск упорядоченного массива

BSL()-бинарный поиск упорядоченного массива

*/
package saod_lab5;
import java.util.Random;
public class Main {
public static void test(int sz) {

int[] m = new int[sz];

int[] m1 = new int[sz + 1];

Random rnd = new Random();

int max, max1, max2, max3;

max = max1 = max2 = max3 = 0;

int av, av1, av2, av3;

av = av1 = av2 = av3 = 0;

for (int t = 0; t < sz; t++) {

for (int i = 0; i < sz; i++) {

m[i] = m1[i] = rnd.nextInt(sz);

}

int f = rnd.nextInt(sz);

int q = QLS(m1, f);

if (q > max) {

max = q;

}

av += q;

int q1 = LS(m, f);

if (q1 > max1) {

max1 = q1;

}

av1 += q1;

m1[sz] = 9999999;

m1 = sort(m1);

m = sort(m);

int q2 = QLSL(m1, f);

if (q2 > max2) {

max2 = q2;

}

av2 += q2;

int q3 = BSL(m, f);

if (q3 > max3) {

max3 = q3;

}

av3 += q3;

}

av /= sz;

av1 /= sz;

av2 /= sz;

av3 /= sz;

System.out.println("Max LS" + " (" + sz + ") :" + max1);

System.out.println("Max QLS" + " (" + sz + ") :" + max);

System.out.println("Max QLSL" + " (" + sz + ") :" + max2);

System.out.println("Max BSL" + " (" + sz + ") :" + max3);

System.out.println("Average LS" + " (" + sz + ") :" + av1);

System.out.println("Average QLS" + " (" + sz + ") :" + av);

System.out.println("Average QLSL" + " (" + sz + ") :" + av2);

System.out.println("Average BSL" + " (" + sz + ") :" + av3);

}
public static int LS(int s[], int p) {

int sz = s.length;

int d = 0;

for (int i = 0; i < sz; i++) {

d++;

d++;

if (p == s[i]) {

break;

}

}

return d;

}
public static int QLS(int s[], int p) {

int sz = s.length;

int d = 0;

int i = 0;

s[sz - 1] = p;

while (true) {

d++;

if (s[i] == s[sz - 1]) {

d++;

if (i == sz - 1) {

break;

}

break;

}

i++;

}

return d;

}
public static int QLSL(int s[], int p) {

int sz = s.length;

int d = 0;

int i = 0;

s[sz - 1] = p;

while (true) {

d++;

if (s[i] == s[sz - 1]) {

d++;

if (i == sz - 1) {

break;

}

d = i + 1;

break;

}

d++;

if (p < s[i]) {

break;

}

i++;

}

return d;

}
public static int BSL(int s[], int p) {

int sz = s.length;

int d = 0;

int r = sz - 1;

int l = 0;

while (r - l > 0) {

d++;

if (s[(r + l) / 2] == p) {

d++;

break;

} else {

d++;

if (s[(r + l) / 2] > p) {

d++;

r = (r + l) / 2;

} else {

d++;

l = (r + l) / 2;

}

}

if (r - l == 1 && s[l] < p && s[r] > p) {

d++;

break;
}

if (r - l == 1) {

d++;

break;

}

}

return d;

}
public static int[] sort(int s[]) {

for (int i = 0; i < s.length; i++) {

int sw = 0;

for (int j = 0; j < s.length - 1; j++) {

if (s[j] > s[j + 1]) {

sw++;

int q = s[j];

s[j] = s[j + 1];

s[j + 1] = q;

}

}

if (sw == 0) {

break;

}

}

return s;

}
public static void main(String[] args) {

test(50);

test(100);

test(150);

test(200);

test(250);

test(300);

test(350);

test(400);

test(450);

}

}

Output:

Max LS (50) :100

Max QLS (50) :52

Max QLSL (50) :102

Max BSL (50) :19

Average LS (50) :66

Average QLS (50) :34

Average QLSL (50) :38

Average BSL (50) :14

Max LS (100) :200

Max QLS (100) :102

Max QLSL (100) :200

Max BSL (100) :22

Average LS (100) :128

Average QLS (100) :65

Average QLSL (100) :67

Average BSL (100) :17

Max LS (150) :300

Max QLS (150) :152

Max QLSL (150) :302

Max BSL (150) :25

Average LS (150) :184

Average QLS (150) :93

Average QLSL (150) :98

Average BSL (150) :18

Max LS (200) :400

Max QLS (200) :202

Max QLSL (200) :388

Max BSL (200) :25

Average LS (200) :256

Average QLS (200) :129

Average QLSL (200) :142

Average BSL (200) :19

Max LS (250) :500

Max QLS (250) :252

Max QLSL (250) :494

Max BSL (250) :25

Average LS (250) :331

Average QLS (250) :167

Average QLSL (250) :169

Average BSL (250) :21

Max LS (300) :600

Max QLS (300) :302

Max QLSL (300) :602

Max BSL (300) :28

Average LS (300) :380

Average QLS (300) :191

Average QLSL (300) :215

Average BSL (300) :21

Max LS (350) :700

Max QLS (350) :352

Max QLSL (350) :702

Max BSL (350) :28

Average LS (350) :437

Average QLS (350) :219

Average QLSL (350) :230

Average BSL (350) :22

Max LS (400) :800

Max QLS (400) :402

Max QLSL (400) :802

Max BSL (400) :28

Average LS (400) :513

Average QLS (400) :257

Average QLSL (400) :263

Average BSL (400) :23

Max LS (450) :900

Max QLS (450) :452

Max QLSL (450) :892

Max BSL (450) :28

Average LS (450) :558

Average QLS (450) :280

Average QLSL (450) :300

Average BSL (450) :23


Результаты работы программы.
Максимальное количество операций сравнения

Алгоритм поиска	Количество элементов в массиве
	50	100	150	200	250	300	350	400	450
Линейный	100	200	300	400	500	600	700	800	900
Быстрый линейный	52	102	152	202	252	302	352	402	452
Быстрый линейный в упоряд. массиве	102	200	302	388	494	602	702	802	892
Бинарный	19	22	25	25	25	28	28	28	28

Среднее количество операций сравнения

Алгоритм поиска	Количество элементов в массиве
	50	100	150	200	250	300	350	400	450
Линейный	66	128	184	256	331	380	437	513	558
Быстрый линейный	34	65	93	129	167	191	219	257	280
Быстрый линейный в упоряд. массиве	38	67	98	142	169	215	230	263	300
Бинарный	14	17	18	19	21	21	22	23	23

Максимальное количество операций сравнения


Среднее количество операций сравнения

Вывод

В ходе исследования алгоритмов поиска, алгоритмы линейного и быстрого поиска упорядоченного массива, по максимальному количеству операции показали примерно одинаковые результаты, так как в линейном поиске при каждом шаге происходит проверка конца массива, а в быстром поиске в сортированном массиве, на каждом шаге проверяется значение, если значение меньше(больше) искомого то дальнейший поиск не имеет смысла, искомого элемента нет в списке. Быстрый линейный поиск показывает среднее значении по всем показателям, так как в этом алгоритме проверяется конец массива только при совпадении значения со значением конца массива. Алгоритм бинарного поиска показывает значительный прирост скорости выполнения алгоритма что показывают и теоретические расчеты O(log2N), не зависимо от размера массива . Средняя скорость выполнения быстрого поиска не зависит от упорядоченности массива, и примерно совпадает при разных размерностях массива.