ХМЕЛЬНИЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
Факультет програмування та комп’ютерних
і телекомунікаційних систем
Кафедра інженерії програмного забезпечення
Лабораторна робота № 1
на тему:
«Аналіз алгоритмів. Порядок росту.»
Виконав:
студент групи ІПЗс-19-1 Стрілець Д.А.
(підпис)
Перевірив:
викладач Бедратюк Г.І.
(підпис)
Хмельницький 2020 р.
Мета: Навчитися оцінювати складність алгоритмів та порівнювати їх між собою.
Хід роботи
Завдання
Для розв’язання деякої обчислювальної задачі використовується два алгоритма A1 і A2 з часовими складностями
та 
Для яких значень n краще використовувати перший алгоритм а для яких другий?
Реалізувати алгоритм MergeSort.
А - Скільки інверсій в масиві {3, 8, 6, 1}
Б – Знайти кількість інверсій в масиві що знаходиться в файлі IntegerArray.txt
Довести, що
Впорядкувати наступні функції в зростаючому порядку відносно їх порядку росту.
а,b,e,c,d
Дати оцінку алгоритму та визначити складність
Визначити складність алгоритмів
Чи віно що
Відповіді
(а) Асимтотично алгоритм А2 кращий, оскільки складність першого алгоритму можна записати як
, а складність другого як 
, це означає, що часова складність першого алгоритма в даному випадку буде більша, тому зручніше використовувати другий алгоритм.(б) Часову складність першого алгоритму можна записати як
, а складність другого як 
, це означає, що часова складність другого алгоритма при невеликих значеннях n буде менша, тому краще використовувати в таких випадках А2 проте дана функція швидко зростає при великих значеннях, тому в таких випадках слід застовувати А1.private void button4_Click(object sender, EventArgs e)
{
counter = 0;
label2.Text = "";
int[] arr = new int[dataGridView1.ColumnCount];
for(int i =0;i< dataGridView1.ColumnCount;i++)
{
arr[i] = Convert.ToInt32(dataGridView1.Rows[0].Cells[i].Value);
}
MergeSort(arr, 0, arr.Length - 1);
for (int i = 0; i < dataGridView1.ColumnCount; i++)
{
dataGridView2.ColumnCount = dataGridView1.ColumnCount;
dataGridView2.Columns[i].Width = 30;
dataGridView2.Rows[0].Cells[i].Value = arr[i];
}
label2.Text = counter.ToString();
}
public void MergeSort(int[] arr,int l ,int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
MergeSort(arr, l, m);
MergeSort(arr, m + 1, r);
Merge(arr, l, m, r);
}
}
int counter = 0;
public void Merge(int[] arr, int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
counter++;
}
else
{
arr[k] = R[j];
j++;
counter++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
А.
Б.
, оскільки в основному зростання часової складності залежить від показника з найвищим степенем , і інші доданки не мають великого значення як і коефіцієнт перед n з найбільшим степенем.Інколи позначення big-O використовують для позначення менше ніж. В даному випадку найвища степінь при описі алгоритму дорівнюватиме 1 що менше ніж 2, тому таке порівняння допустиме.
Так як і в попередньому прикладі степінь буде меншим тобто 2 і порівняння також можна застосувати.
Відповідь - а,b,e,c,d
n^2
O(logb)
Запитання:
Дати означення алгоритму.
Задача сортування.
Алгоритм сортування вставками.
Аналіз алгоритмів. Порядок росту функції.
Цикловий інваріант та його використання.
Аналіз алгоритму сортування вставками.
Алгоритм MERGESORT.
Аналіз алгоритму MERGESORT.
Метод побудови алгоритмів «поділяй та володарюй», його часова складність.
Відповіді:
Алгоритм це певна чітка послідовність дій, що призводить до певного результату.
Це алгоритм який здійснює впорядкування даних в порядку зростання чи спадання.
Даний алгоритм передбачає порівняння кожного елементу масиву з усіма попередніми та встановлення його в правильну позицію.
Це процес визначення обчислювальної складності алгоритмів, тобто кількості часу, пам'яті чи інших ресурсів, необхідних для виконання алгоритмів. Основний критерій це кількість кроків що здійснює алгоритм для виконання певної задачі. Порядок росту функції відповідає часу що затрачається на виконання алгоритму.
Інваріант — це умова, що не змінюється, або не повинна змінюватись коли система працює правильно. Інваріанти використовують при проектуванні циклічних алгоритмів.
Швидкодія даного алгоритму = n2/4, і він є більш ефективний ніж деякі квадратичні алгоритми сортування, наприклад сортування вибіркою і бульбашкою.
Алгоритм полягає в поділі масиву елементів навпіл, після чого виконуються індентичні дії з підмасивами, доки вони стануть неподільними, потім проводиться порівняння окремих елементів і масиви з’єднуються в один і так поки не утвориться один посортований масив.
Даний алгоритм потребує часу для поділу масиву, сортуванню половинок та поєднанню масивів в один, тому час роботи всього алгоритму становить О(n log n). Крім цього алгоритм потребує додатково місця, що інколи не є доступним.
Парадигма розробки алгоритмів , яка полягає в рекурсивном розбитті розв'язуваної задачі на дві або більше підзадачі того ж типу, але меншого розміру, і комбінуванні їх рішень для отримання відповіді до вихідної задачі; розбиття виконуються до тих пір, поки всі підзадачі не опиняться елементарними.