Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Асимптотичні характеристики складності алгоритму;алгоритм з поліноміальною та експоненціальною складністю
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра ЕОМ
Звіт
до лабораторної роботи № 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;
}
Висновок:
Ознайомився з асимптотичними характеристиками складності та класами складності алгоритмів.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора