Курсовая работа - Сравнительный анализ метода Шелла и метода Бэтчера по критерию эффективности

Подождите немного. Документ загружается.

ГЛАВА 3 СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ШЕЛЛА И

БЭТЧЕРА ПО КРИТЕРИЮ ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ К

РАЗЛИЧНЫМ ИСХОДНЫМ ДАННЫМ

3.1 Исследование метода Шелла посредством построения

линейного уравнения регрессии

Сначала были собраны исходные данные. Созданные на Turbo Pascal

7.0 программы запускались с исходными массивами от одного до 200

элементов, подсчитывалось число сравнений и перестановок для каждой

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

значения перестановок, сравнений, неупорядоченных элементов и

размерностей исходных массивов.

Таблица 2

Исходные данные для искомой эконометрической модели

группа х1 х2 У

от 1 до 20 66 17,75 12,5

от 21 до 50 365,25 54,5 31

от 51 до 100 2011 228,5 71

от 101 до 150 5888,75 595,75 124,5

от 151 до 200 11740,5 919,75 176,5

итого: 20071,5 1816,25 415,5

сред.знач. 4014,3 363,25 83,1

Теперь нужно определить характер связи между основным показателем

эффективности алгоритма сортировки y= Pr+Sr и характеристиками

исходных данных. Для этого вычисляем парные коэффициенты корреляции

yx1

, ryx2 , rx1x2. В нашем случае эти коэффициенты равны:

Rx1y=0,9748445

Rx2y=0,9930315

Rx1x2=0,9898675

Это означает, что связь между этими переменными прямая (все

показатели положительные) и сильная (коэффициенты близки по значению к

1), т.е. с увеличением одного показателя другой возрастает.

Уравнение регрессии.

Выберем уравнение регрессии для построения регрессионной модели.

Общий вид уравнения, выражающего зависимость между количеством

элементов в массиве, числом находящихся не на месте элементов, числом их

сравнений и перестановок будет линейным:

),,,,,(

210321

22110

aaaxxxQy

xaxaa



Для нахождения коэффициентов а

, а

применим метод наименьших

квадратов.

Выполнение расчётов, необходимые для формирования системы

нормальных уравнений были произведены в MS Excel.

На основании полученных коэффициентов составляем систему

нормальных уравнений в матричном виде:

Таблица 3

Система нормальных уравнений в матричном виде

а0 а1 а2 У

5 20071,5 1816,25 415,5

20071,5

17669860

1,4 14787139 2960276,38

1816,25

14787138,

81 1256355,7 254641,625

Вычислим главный определитель системы, если он отличен от нуля, то

система имеет решение и его можно получить методом Крамера.

С помощью функции МОПРЕД() получим значение главного

определителя системы:

Главный определитель D  0. Теперь вычисляем другие определители,

требуемые для нахождения переменных а

, а

. Считаем определитель D

полученный из главного заменой первого столбца а

на вектор У:

Таблица 4

Матрица для вычисления определителя D

У а1 а2

415,5 20071,5 1816,25

2960276,38 176698601,4 14787139

254641,625 14787138,81 1256355,7

Получаем значение коэффициента а

делением D1 на D:



16,89813

Считаем с помощью функции МОПРЕД() определитель D

, полученный

из главного заменой второго столбца а

на вектор У:

Таблица 5

Матрица для вычисления определителя D

Δ=5,78143E+12

Δ1=9,76953E+13

a0 y а2

5 415,5 1816,25

20071,5

2960276,3

75 14787139

1816,25

254641,62

5 1256355,7

Δ2=32130895219

Получаем значение коэффициента а1 делением D2 на D:



-0,0055576

Считаем с помощью функции МОПРЕД() определитель D

, полученный

из главного заменой третьего столбца а

на вектор У:

Таблица 6

Матрица для вычисления определителя D

а0 а1 У

5 20071,5 415,5

20071,5 176698601,4 2960276,4

1816,25 14787138,81 254641,63

Δ3=1,40874E+12

Получаем значение коэффициента а

делением D

на D:



0,2436663

Получили уравнение регрессионной модели:

y=16,89813-0,0055576*x1 +0,2436663*x2

Эластичность.

Влияние отдельных факторов в многофакторных моделях может быть

охарактеризовано с помощью частных коэффициентов эластичности,

которые показывают, на сколько процентов изменится результативный

признак, если значение одного из факторных признаков изменится на 1 %, а

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

регрессионной модели:

Эyx1=-0,268470485

Эyx2=1,065123555

Это означает, что если среднее количество элементов возрастёт на 1 %,

то количество перестановок возрастет на 1,065123555%, если количество

элементов возрастёт на 1 %, то количество сравнений уменьшится на

0,268470485%.

Коэффициент детерминации и коэффициент множественной

корреляции.

На их основании можно сделать заключение о значимости построенной

регрессионной модели и возможности её дальнейшего использования для

объяснения и анализа метода сравнения, проявляющегося в данной задаче

при сортировке элементов одномерных массивов.

Найдем необходимые коэффициенты.

Таблица 7

Матрица корреляции факторных признаков x1, x2

• x1 x2

x1 1 0,9898675

x2 0,9898675 1

Таблица 8

Обратная матрица корреляции

49,597437

05 -49,094891

49,09489102 49,597437

Таблица 9

Вектор коэффициентов парной регрессии результативного признака y и

факторных признаков x1, x2

rx1y=

0,97484

rx2y=

0,99303

На основании приведённых исходных данных получаем коэффициент

множественной корреляции:

Rxy=0,9893859

Коэффициент детерминации:

D=0,9788844

Так как коэффициент детерминации больше 0,5, это указывает на

довольно высокую достоверность построенной регрессионной модели,

поэтому возможно её применение для объяснения процессов сортировки.

3.2 Исследование сортировки методом Бетчера посредством

построения линейного уравнения регрессии

Сначала были собраны исходные данные. Созданные на Turbo Pascal

7.0 программы запускались с исходными массивами от одного до 200

элементов, подсчитывалось число сравнений и перестановок для каждой

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

значения перестановок, сравнений, неупорядоченных элементов и

размерностей исходных массивов.

Таблица 10

Исходные данные

группа У Х1 Х2

от 1 до 20 12 47 17

от 21 до 50 22 127 43

от 51 до 100 66 598 405

от 101 до 150 116 1326 405

от 151 до 200 156 1612 472

сумма 372 3710 1342

ср.знач. 74,4 742 268,4

Парные коэффициенты корреляции r

yx1

, ryx2 , rx1x2:

Ryx1=0,995296396

Ryx2=0,901676587

Rx1x2=0,891177289

Это означает, что связь между этими переменными прямая (все

показатели положительные) и сильная (коэффициенты близки по значению к

1), т.е. с увеличением одного показателя другой возрастает.

Уравнение регрессии.

Уравнение регрессии будет линейного вида. Для нахождения

применим метод наименьших квадратов.

Таблица 11

Система нормальных уравнений в матричном виде

а0 а1 а2 У

5 3710 1342 372

3710 4732762

1546

344

448

114

1342 1546344

5529

148

492

Считаем главный определитель, другие определители, а также

вычисляем коэффициенты а

, а

Таблица 12

Определители системы нормальных уравнений в матричном виде

гл.опред. 3,92766E+11

det(a0) 3,40446E+12

det(a1) 31955985760

det(a2) 7846611312



8,667885795 ;



0,081361283;



0,019977802

Получили уравнение регрессионной модели:

Y=8,667885795 +0,081361283*x1 + 0,019977802*x2

Эластичность.

Влияние отдельных факторов в многофакторных моделях может быть

охарактеризовано с помощью частных коэффициентов эластичности,

которые показывают, на сколько процентов изменится результативный

признак, если значение одного из факторных признаков изменится на 1 %, а

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

регрессионной модели

Эyx1=0,811426

Эyx2=0,07207

Это означает, что если средний размер одномерного массива данных

возрастёт на 1 %, то количество операций сравнений увеличится на

0,811426%, а количество перестановок возрастет на 0,07207%.

Коэффициент детерминации и коэффициент множественной корреляции.

Таблица 13

Матрица корреляции факторных признаков x1, x2

0,89

1177

0,89

1177 1

Таблица 14

Обратная матрица корреляции

4,85901474 -4,33024

-4,330243584 4,859015

Таблица 15

Вектор коэффициентов парной регрессии результативного признака y и

факторных признаков x1, x2

rx1y 0,995296

rx2y 0,901677

На основании приведённых исходных данных получаем коэффициент

множественной корреляции:

Rxy = 0,991663622

Коэффициент детерминации:

D = 0,983396738

Так как коэффициент детерминации больше 0,5, это указывает на

довольно высокую достоверность построенной регрессионной модели,

поэтому возможно её применение для объяснения процессов сортировки.