Асимптотичні характеристики складності алгоритму;алгоритм з поліноміальною та експоненціальною складністю. Звіт до лабораторної роботи з Алгоритми та методи обчислень. Робота № 101174

Асимптотичні характеристики складності алгоритму;алгоритм з поліноміальною та експоненціальною складністю

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2025

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Алгоритми та методи обчислень

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра ЕОМ Звіт до лабораторної роботи № 2 З дисципліни «Алгоритми та методи обчислень» На тему: «Асимптотичні характеристики складності алгоритму;алгоритм з поліноміальною та експоненціальною складністю» / Завдання / Варіант по списку: 24. Варіант завдання: 24 /Перше правило декларує, що постійні множники не мають значення для визначення порядку зростання. Друге правило називається "Правило сум". Це правило використовується для послідовних програмних фрагментів з циклами та розгалуженнями. Порядок зростання скінченої послідовності програмних фрагментів (без врахування констант) дорівнює порядку зростання фрагменту з найбільшою часовою складністю. Якщо алгоритм складається з двох фрагментів, функції часових складностей яких L1(n) і L2(n) мають ступені зростання O(f(n)) і O(g(n)) відповідно, то алгоритм має степінь зростання O(max(f(n),g(n))). Третє правило називається "Правило добутків". Якщо L1(n) і L2(n) мають ступені зростання O(f(n)) і O(g(n)) відповідно, то добуток L1(n) L2(n) має степінь зростання O(f(n)g(n)) . Прикладом може бути фрагмент програми "цикл в циклі". Задані функції часової складності L(n) для чотирьох алгоритмів: ? 1 ? =/ ? 2 ? = / ? 3 ? =/ ? 4 ? =/ Використавши правило сум і правило добутків знайдемо O(n) : ? 1 ? =/ ? 2 ? =/ ? 3 ? =?! ? 4 ? = ? Розташуємо функції Oi(n) у порядку зростання: ? 4 ? ? 1 ? ? 2 ? ? 3 ? Функція O4(n) = ?! має найбільший степінь зростання. Побудуємо графіки для Y(n) = ? 2 ? ? ? ? для n = (1 … 10) k (5,6,7) Для спрощення будемо вважати що поліном для відповідних значень K буде прирівнюватися до (??? 2 ?) 2 , (??? 2 ?) 3 та (??? 2 ?) 4 , оскільки ці значення є тою адитивною складовою в поліномі, яка найшвидше зростає. Y(n) = ?! ? ? ??? 2 n : / Y(n) = ?! ? ? ??? 2 n : / Y(n) = ?! ? ? ??? 2 n : / Алгоритм рішення завдання Код програми #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <time.h> #include "bmp.h" #define SIZE 512 #define SCALE 32 double factorial(double arg) { if(arg < 1.0) return 1; return arg * factorial(arg-1); } double drawPlotForFunction(double arg, int k) { return factorial(arg)/pow(arg,k)*log2(arg); } void drawPlot(double(*functionPtr)(double arg, int k), BMP * bmpPtr, UINT Size, UCHAR pt, UINT scale, int k) { for (int x_ = 0; x_ <= Size; x_++) { int x = (int)(x_); double y = scale*((double)(functionPtr((double)x_/scale,k))); BMP_SetPixelIndex(bmpPtr, x + 10, Size - y - 10 , pt); } } void mark(BMP * bmpPtr, int xSize, int ySize, UCHAR pt, int scale) { for (int x = 0;x<xSize;x+=scale) { for(int y = 0;y<10;++y) BMP_SetPixelIndex(bmpPtr, x, ySize - y, pt); } for (int y = 0;y<ySize;y+=scale) { for(int x = 0;x<10;++x) BMP_SetPixelIndex(bmpPtr, x, ySize - y, pt); } } int main(int argc, char* argv[]) { BMP *plot1bmp, *plot2bmp, *plot3bmp; UCHAR r = 0xff, g = 0xff, b = 0xff; plot1bmp = BMP_Create(SIZE, SIZE, 8); BMP_CHECK_ERROR(stderr, -3); plot2bmp = BMP_Create(SIZE, SIZE, 8); BMP_CHECK_ERROR(stderr, -3); plot3bmp = BMP_Create(SIZE, SIZE, 8); BMP_CHECK_ERROR(stderr, -3); BMP_SetPaletteColor(plot1bmp, 2, 0, g, 0); BMP_SetPaletteColor(plot1bmp, 1, r, 0, 0); BMP_SetPaletteColor(plot1bmp, 0, 0, 0, 0); BMP_SetPaletteColor(plot2bmp, 2, 0, g, 0); BMP_SetPaletteColor(plot2bmp, 1, r, 0, 0); BMP_SetPaletteColor(plot2bmp, 0, 0, 0, 0); BMP_SetPaletteColor(plot3bmp, 2, 0, g, 0); BMP_SetPaletteColor(plot3bmp, 1, r, 0, 0); BMP_SetPaletteColor(plot3bmp, 0, 0, 0, 0); mark(plot1bmp, SIZE, SIZE, 1, SCALE); drawPlot(drawPlotForFunction, plot1bmp, SIZE, 2, SCALE, 3); mark(plot2bmp, SIZE, SIZE, 1, SCALE); drawPlot(drawPlotForFunction, plot2bmp, SIZE, 2, SCALE, 4); mark(plot3bmp, SIZE, SIZE, 1, SCALE); drawPlot(drawPlotForFunction, plot3bmp, SIZE, 2, SCALE, 5); BMP_WriteFile(plot1bmp, "plot1.bmp"); BMP_CHECK_ERROR(stderr, -5); BMP_WriteFile(plot2bmp, "plot2.bmp"); BMP_CHECK_ERROR(stderr, -5); BMP_WriteFile(plot3bmp, "plot3.bmp"); BMP_CHECK_ERROR(stderr, -5); BMP_Free(plot1bmp); BMP_Free(plot2bmp); BMP_Free(plot3bmp); return 0; } Висновок: Ознайомився з асимптотичними характеристиками складності та класами складності алгоритмів.

Звіт до лабораторної роботи Алгоритми та методи обчислень

13.06.2025 08:45

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись