МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
Лабораторна робота № 2
Асимптотичні характеристики складності алгоритму;
алгоритми з поліноміальною та експоненціальною складністю.з дисципліни
" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
1. МЕТА РОБОТИ
Ознайомитись з асимптотичними характеристиками складності
та класами складності алгоритмів.
ТЕОРЕТИЧНІ ВІДОМОСТІ
1.1. Часова складність.
В процесі розв’язку задачі вибір алгоритму викликає певні труднощі. Алгоритм
повинен задовільняти вимогам, які часом суперечать одна одній:
бути простим для розуміння, переводу в програмний код, відлагодження.
ефективно використовувати комп'ютерні ресурси і виконуватись швидко.
Якщо програма повинна виконуватись декілька разів, то перша вимога більш
важлива. Вартість робочого часу програміста перевищує вартість машинного часу
виконання програми, тому вартість програми оптимізується по вартості написання, а не
виконання програми. Якщо задача вимагає значних обчислювальних витрат, то вартість
виконання програми може перевищити вартість написання програми, особливо коли
програма повинна виконуватись багаторазово. Але навіть в цій ситуації доцільно спочатку
реалізувати простий алгоритм, і з'ясувати яким чином повинна себе поводити більш
складна програма.
На час виконання програми впливають наступні чинники:
ввід інформації в програму;
якість скомпільованого коду;
машинні інструкції, які використовуються для виконання програми;
часова складність алгоритму(ЧС).
Часова складність є функцією від вхідних даних. Для деяких задач ЧС залежить від
самих вхідних даних (знаходження найбільшого спільного дільника двох чисел), для
інших – від їх "розміру" (задачі сортування).
Коли ЧС є функцією від самих даних, її визначають як ЧС для найгіршого випадку,
тобто як найбільшу кількість інструкцій програми серед всіх можливих вхідних даних для
цього алгоритму.
Використовується також ЧС в середньому випадку (в статистичному сенсі), як
середня кількість інструкцій по всім можливим вхідним даним. На практиці ЧС в
середньому випадку важче визначити ніж ЧС для найгіршого випадку, через те що це
математично важка для розв'язання задача. Крім того, іноді важко визначити, що означає
"середні" вхідні дані.
Коли ЧС є функцією від кількості вхідних даних, аналізується швидкість зростання
цієї функції.Код програми
// don't forget to use compilation key for Linux: -lm
#define _CRT_SECURE_NO_WARNINGS // for using fopen in VS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#ifndef UINT
#define UINT unsigned long int
#endif
#ifndef USHORT
#define USHORT unsigned short
#endif
#ifndef UCHAR
#define UCHAR unsigned char
#endif
#define QDBMP_VERSION_MAJOR 1
#define QDBMP_VERSION_MINOR 0
#define QDBMP_VERSION_PATCH 1
typedef enum
{
BMP_OK = 0,
BMP_ERROR,
BMP_OUT_OF_MEMORY,
BMP_IO_ERROR,
BMP_FILE_NOT_FOUND,
BMP_FILE_NOT_SUPPORTED,
BMP_FILE_INVALID,
BMP_INVALID_ARGUMENT,
BMP_TYPE_MISMATCH,
BMP_ERROR_NUM
} BMP_STATUS;
typedef struct _BMP BMP;
BMP* BMP_Create(UINT width, UINT height, USHORT depth);
void BMP_Free(BMP* bmp);
BMP* BMP_ReadFile(const char* filename);
void BMP_WriteFile(BMP* bmp, const char* filename);
UINT BMP_GetWidth(BMP* bmp);
UINT BMP_GetHeight(BMP* bmp);
USHORT BMP_GetDepth(BMP* bmp);
void BMP_GetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR* r, UCHAR* g, UCHAR* b);
void BMP_SetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR r, UCHAR g, UCHAR b);
void BMP_GetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR* val);
void BMP_SetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR val);
void BMP_GetPaletteColor(BMP* bmp, UCHAR index, UCHAR* r, UCHAR* g, UCHAR* b);
void BMP_SetPaletteColor(BMP* bmp, UCHAR index, UCHAR r, UCHAR g, UCHAR b);
BMP_STATUS BMP_GetError();
const char* BMP_GetErrorDescription();
#define PALETTE_SIZE 256
#define OUTPUT_WIDTH 512
#define OUTPUT_HEIGHT 512
#define RECTANGLE_WIDTH ( OUTPUT_WIDTH / 16 )
#define RECTANGLE_HEIGHT ( OUTPUT_HEIGHT / 16 )
#define BMP_CHECK_ERROR( output_file, return_value ) \
if (BMP_GetError() != BMP_OK) \
{ \
fprintf((output_file), "BMP error: %s\n", BMP_GetErrorDescription()); \
return(return_value); \
} \
void mark(BMP * bmpPtr, UINT o, UINT xSize, UINT ySize, UCHAR pt){
UINT o2 = 2 * o;
UINT xO, yO;
UINT fraction;
for (UINT x = 0; x < xSize; ++x){
for (UINT y = 0; !y || (!(x % 20) && y < 10); ++y){
for (xO = 0; xO <= o2; ++xO){
for (yO = 0; yO <= o2; ++yO){
if (x + xO >= o && x + xO - o < xSize && y + yO >= o && y + yO - o < ySize){
BMP_SetPixelIndex(bmpPtr, x + xO - o, ySize - (y + yO - o), pt);
}
}
}
}
}
for (UINT y = 0; y < ySize; ++y){
for (UINT x = 0; !x || (!(y % 20) && x < 10); ++x){
for (xO = 0; xO <= o2; ++xO){
for (yO = 0; yO <= o2; ++yO){
if (x + xO >= o && x + xO - o < xSize && y + yO >= o && y + yO - o < ySize){
BMP_SetPixelIndex(bmpPtr, x + xO - o, ySize - (y + yO - o), pt);
}
}
}
}
}
}
double functionForTabulate(double arg){
return arg * arg / 500.;
}
void tabulate(double(*functionPtr)(double arg), BMP * bmpPtr, UINT o, UINT xSize, UINT ySize, UCHAR pt){
UINT o2 = 2 * o;
UINT xO, yO;
UINT fraction;
for (UINT x = 0; x < xSize; ++x){
for (fraction = 0; fraction < 32; ++fraction){
double fX = (double)fraction / (double)32 + (double)x;
UINT y = (UINT)functionPtr(fX);
for (xO = 0; xO <= o2; ++xO){
for (yO = 0; yO <= o2; ++yO){
if (x + xO >= o && x + xO - o < xSize && y + yO >= o && y + yO - o < ySize){
BMP_SetPixelIndex(bmpPtr, x + xO - o, ySize - (y + yO - o), pt);
}
}
}
}
}
}
int main(int argc, char* argv[])
{
BMP* output;
UCHAR r = 0xff, g = 0xff, b = 0xff;
output = BMP_Create(OUTPUT_WIDTH, OUTPUT_HEIGHT, 8);
BMP_CHECK_ERROR(stderr, -3);
BMP_SetPaletteColor(output, 3, 0, 0, 255);
BMP_SetPaletteColor(output, 2, 0, 255, 0);
BMP_SetPaletteColor(output, 1, 255, 0, 0);
BMP_SetPaletteColor(output, 0, 0, 0, 0);
mark(output, 0, 512, 512, 1);
tabulate(functionForTabulate, output, 0, 512, 512, 2);
BMP_WriteFile(output, "out.bmp");
BMP_CHECK_ERROR(stderr, -5);
BMP_Free(output);
printf("Result writed to \"out.bmp\".\r\n");
printf("An example file may be located:\r\n");
printf(" \"..\\Visual Studio 2013\\Projects\\amolab2\\amolab2\\out.bmp\"\r\n");
printf("After closing the program, open it manually.\r\n\r\n");
printf("Press any key to continue . . .");
getchar();
return 0;
}
/*********************************** BMP Implementation **********************************/
/* Bitmap header */
typedef struct _BMP_Header
{
USHORT Magic; /* Magic identifier: "BM" */
UINT FileSize; /* Size of the BMP file in bytes */
USHORT Reserved1; /* Reserved */
USHORT Reserved2; /* Reserved */
UINT DataOffset; /* Offset of image data relative to the file's start */
UINT HeaderSize; /* Size of the header in bytes */
UINT Width; /* Bitmap's width */
UINT Height; /* Bitmap's height */
USHORT Planes; /* Number of color planes in the bitmap */
USHORT BitsPerPixel; /* Number of bits per pixel */
UINT CompressionType; /* Compression type */
UINT ImageDataSize; /* Size of uncompressed image's data */
UINT HPixelsPerMeter; /* Horizontal resolution (pixels per meter) */
UINT VPixelsPerMeter; /* Vertical resolution (pixels per meter) */
UINT ColorsUsed; /* Number of color indexes in the color table that are actually used by the bitmap */
UINT ColorsRequired; /* Number of color indexes that are required for displaying the bitmap */
} BMP_Header;
/* Private data structure */
struct _BMP
{
BMP_Header Header;
UCHAR* Palette;
UCHAR* Data;
};
/* Holds the last error code */
static BMP_STATUS BMP_LAST_ERROR_CODE = 0;
/* Error description strings */
static const char* BMP_ERROR_STRING[] =
{
"",
"General error",
"Could not allocate enough memory to complete the operation",
"File input/output error",
"File not found",
"File is not a supported BMP variant (must be uncompressed 8, 24 or 32 BPP)",
"File is not a valid BMP image",
"An argument is invalid or out of range",
"The requested action is not compatible with the BMP's type"
};
/* Size of the palette data for 8 BPP bitmaps */
#define BMP_PALETTE_SIZE ( 256 * 4 )
int ReadHeader(BMP* bmp, FILE* f);
int WriteHeader(BMP* bmp, FILE* f);
int ReadUINT(UINT* x, FILE* f);
int ReadUSHORT(USHORT *x, FILE* f);
int WriteUINT(UINT x, FILE* f);
int WriteUSHORT(USHORT x, FILE* f);
BMP* BMP_Create(UINT width, UINT height, USHORT depth)
{
BMP* bmp;
int bytes_per_pixel = depth >> 3;
UINT bytes_per_row;
if (height <= 0 || width <= 0)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
return NULL;
}
if (depth != 8 && depth != 24 && depth != 32)
{
BMP_LAST_ERROR_CODE = BMP_FILE_NOT_SUPPORTED;
return NULL;
}
/* Allocate the bitmap data structure */
bmp = calloc(1, sizeof(BMP));
if (bmp == NULL)
{
BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY;
return NULL;
}
/* Set header' default values */
bmp->Header.Magic = 0x4D42;
bmp->Header.Reserved1 = 0;
bmp->Header.Reserved2 = 0;
bmp->Header.HeaderSize = 40;
bmp->Header.Planes = 1;
bmp->Header.CompressionType = 0;
bmp->Header.HPixelsPerMeter = 0;
bmp->Header.VPixelsPerMeter = 0;
bmp->Header.ColorsUsed = 0;
bmp->Header.ColorsRequired = 0;
/* Calculate the number of bytes used to store a single image row. This is always
rounded up to the next multiple of 4. */
bytes_per_row = width * bytes_per_pixel;
bytes_per_row += (bytes_per_row % 4 ? 4 - bytes_per_row % 4 : 0);
/* Set header's image specific values */
bmp->Header.Width = width;
bmp->Header.Height = height;
bmp->Header.BitsPerPixel = depth;
bmp->Header.ImageDataSize = bytes_per_row * height;
bmp->Header.FileSize = bmp->Header.ImageDataSize + 54 + (depth == 8 ? BMP_PALETTE_SIZE : 0);
bmp->Header.DataOffset = 54 + (depth == 8 ? BMP_PALETTE_SIZE : 0);
/* Allocate palette */
if (bmp->Header.BitsPerPixel == 8)
{
bmp->Palette = (UCHAR*)calloc(BMP_PALETTE_SIZE, sizeof(UCHAR));
if (bmp->Palette == NULL)
{
BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY;
free(bmp);
return NULL;
}
}
else
{
bmp->Palette = NULL;
}
/* Allocate pixels */
bmp->Data = (UCHAR*)calloc(bmp->Header.ImageDataSize, sizeof(UCHAR));
if (bmp->Data == NULL)
{
BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY;
free(bmp->Palette);
free(bmp);
return NULL;
}
BMP_LAST_ERROR_CODE = BMP_OK;
return bmp;
}
void BMP_Free(BMP* bmp)
{
if (bmp == NULL)
{
return;
}
if (bmp->Palette != NULL)
{
free(bmp->Palette);
}
if (bmp->Data != NULL)
{
free(bmp->Data);
}
free(bmp);
BMP_LAST_ERROR_CODE = BMP_OK;
}
BMP* BMP_ReadFile(const char* filename)
{
BMP* bmp;
FILE* f;
if (filename == NULL)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
return NULL;
}
/* Allocate */
bmp = calloc(1, sizeof(BMP));
if (bmp == NULL)
{
BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY;
return NULL;
}
/* Open file */
f = fopen(filename, "rb");
if (f == NULL)
{
BMP_LAST_ERROR_CODE = BMP_FILE_NOT_FOUND;
free(bmp);
return NULL;
}
/* Read header */
if (ReadHeader(bmp, f) != BMP_OK || bmp->Header.Magic != 0x4D42)
{
BMP_LAST_ERROR_CODE = BMP_FILE_INVALID;
fclose(f);
free(bmp);
return NULL;
}
/* Verify that the bitmap variant is supported */
if ((bmp->Header.BitsPerPixel != 32 && bmp->Header.BitsPerPixel != 24 && bmp->Header.BitsPerPixel != 8)
|| bmp->Header.CompressionType != 0 || bmp->Header.HeaderSize != 40)
{
BMP_LAST_ERROR_CODE = BMP_FILE_NOT_SUPPORTED;
fclose(f);
free(bmp);
return NULL;
}
/* Allocate and read palette */
if (bmp->Header.BitsPerPixel == 8)
{
bmp->Palette = (UCHAR*)malloc(BMP_PALETTE_SIZE * sizeof(UCHAR));
if (bmp->Palette == NULL)
{
BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY;
fclose(f);
free(bmp);
return NULL;
}
if (fread(bmp->Palette, sizeof(UCHAR), BMP_PALETTE_SIZE, f) != BMP_PALETTE_SIZE)
{
BMP_LAST_ERROR_CODE = BMP_FILE_INVALID;
fclose(f);
free(bmp->Palette);
free(bmp);
return NULL;
}
}
else /* Not an indexed image */
{
bmp->Palette = NULL;
}
/* Allocate memory for image data */
bmp->Data = (UCHAR*)malloc(bmp->Header.ImageDataSize);
if (bmp->Data == NULL)
{
BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY;
fclose(f);
free(bmp->Palette);
free(bmp);
return NULL;
}
/* Read image data */
if (fread(bmp->Data, sizeof(UCHAR), bmp->Header.ImageDataSize, f) != bmp->Header.ImageDataSize)
{
BMP_LAST_ERROR_CODE = BMP_FILE_INVALID;
fclose(f);
free(bmp->Data);
free(bmp->Palette);
free(bmp);
return NULL;
}
fclose(f);
BMP_LAST_ERROR_CODE = BMP_OK;
return bmp;
}
void BMP_WriteFile(BMP* bmp, const char* filename)
{
FILE* f;
if (filename == NULL)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
return;
}
/* Open file */
f = fopen(filename, "wb");
if (f == NULL)
{
BMP_LAST_ERROR_CODE = BMP_FILE_NOT_FOUND;
return;
}
/* Write header */
if (WriteHeader(bmp, f) != BMP_OK)
{
BMP_LAST_ERROR_CODE = BMP_IO_ERROR;
fclose(f);
return;
}
/* Write palette */
if (bmp->Palette)
{
if (fwrite(bmp->Palette, sizeof(UCHAR), BMP_PALETTE_SIZE, f) != BMP_PALETTE_SIZE)
{
BMP_LAST_ERROR_CODE = BMP_IO_ERROR;
fclose(f);
return;
}
}
/* Write data */
if (fwrite(bmp->Data, sizeof(UCHAR), bmp->Header.ImageDataSize, f) != bmp->Header.ImageDataSize)
{
BMP_LAST_ERROR_CODE = BMP_IO_ERROR;
fclose(f);
return;
}
BMP_LAST_ERROR_CODE = BMP_OK;
fclose(f);
}
UINT BMP_GetWidth(BMP* bmp)
{
if (bmp == NULL)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
return -1;
}
BMP_LAST_ERROR_CODE = BMP_OK;
return (bmp->Header.Width);
}
UINT BMP_GetHeight(BMP* bmp)
{
if (bmp == NULL)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
return -1;
}
BMP_LAST_ERROR_CODE = BMP_OK;
return (bmp->Header.Height);
}
USHORT BMP_GetDepth(BMP* bmp)
{
if (bmp == NULL)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
return -1;
}
BMP_LAST_ERROR_CODE = BMP_OK;
return (bmp->Header.BitsPerPixel);
}
void BMP_GetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR* r, UCHAR* g, UCHAR* b)
{
UCHAR* pixel;
UINT bytes_per_row;
UCHAR bytes_per_pixel;
if (bmp == NULL || x < 0 || x >= bmp->Header.Width || y < 0 || y >= bmp->Header.Height)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
}
else
{
BMP_LAST_ERROR_CODE = BMP_OK;
bytes_per_pixel = bmp->Header.BitsPerPixel >> 3;
/* Row's size is rounded up to the next multiple of 4 bytes */
bytes_per_row = bmp->Header.ImageDataSize / bmp->Header.Height;
/* Calculate the location of the relevant pixel (rows are flipped) */
pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x * bytes_per_pixel);
/* In indexed color mode the pixel's value is an index within the palette */
if (bmp->Header.BitsPerPixel == 8)
{
pixel = bmp->Palette + *pixel * 4;
}
/* Note: colors are stored in BGR order */
if (r) *r = *(pixel + 2);
if (g) *g = *(pixel + 1);
if (b) *b = *(pixel + 0);
}
}
void BMP_SetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR r, UCHAR g, UCHAR b)
{
UCHAR* pixel;
UINT bytes_per_row;
UCHAR bytes_per_pixel;
if (bmp == NULL || x < 0 || x >= bmp->Header.Width || y < 0 || y >= bmp->Header.Height)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
}
else if (bmp->Header.BitsPerPixel != 24 && bmp->Header.BitsPerPixel != 32)
{
BMP_LAST_ERROR_CODE = BMP_TYPE_MISMATCH;
}
else
{
BMP_LAST_ERROR_CODE = BMP_OK;
bytes_per_pixel = bmp->Header.BitsPerPixel >> 3;
/* Row's size is rounded up to the next multiple of 4 bytes */
bytes_per_row = bmp->Header.ImageDataSize / bmp->Header.Height;
/* Calculate the location of the relevant pixel (rows are flipped) */
pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x * bytes_per_pixel);
/* Note: colors are stored in BGR order */
*(pixel + 2) = r;
*(pixel + 1) = g;
*(pixel + 0) = b;
}
}
void BMP_GetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR* val)
{
UCHAR* pixel;
UINT bytes_per_row;
if (bmp == NULL || x < 0 || x >= bmp->Header.Width || y < 0 || y >= bmp->Header.Height)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
}
else if (bmp->Header.BitsPerPixel != 8)
{
BMP_LAST_ERROR_CODE = BMP_TYPE_MISMATCH;
}
else
{
BMP_LAST_ERROR_CODE = BMP_OK;
/* Row's size is rounded up to the next multiple of 4 bytes */
bytes_per_row = bmp->Header.ImageDataSize / bmp->Header.Height;
/* Calculate the location of the relevant pixel */
pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x);
if (val) *val = *pixel;
}
}
void BMP_SetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR val)
{
UCHAR* pixel;
UINT bytes_per_row;
if (bmp == NULL || x < 0 || x >= bmp->Header.Width || y < 0 || y >= bmp->Header.Height)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
}
else if (bmp->Header.BitsPerPixel != 8)
{
BMP_LAST_ERROR_CODE = BMP_TYPE_MISMATCH;
}
else
{
BMP_LAST_ERROR_CODE = BMP_OK;
/* Row's size is rounded up to the next multiple of 4 bytes */
bytes_per_row = bmp->Header.ImageDataSize / bmp->Header.Height;
/* Calculate the location of the relevant pixel */
pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x);
*pixel = val;
}
}
void BMP_GetPaletteColor(BMP* bmp, UCHAR index, UCHAR* r, UCHAR* g, UCHAR* b)
{
if (bmp == NULL)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
}
else if (bmp->Header.BitsPerPixel != 8)
{
BMP_LAST_ERROR_CODE = BMP_TYPE_MISMATCH;
}
else
{
if (r) *r = *(bmp->Palette + index * 4 + 2);
if (g) *g = *(bmp->Palette + index * 4 + 1);
if (b) *b = *(bmp->Palette + index * 4 + 0);
BMP_LAST_ERROR_CODE = BMP_OK;
}
}
void BMP_SetPaletteColor(BMP* bmp, UCHAR index, UCHAR r, UCHAR g, UCHAR b)
{
if (bmp == NULL)
{
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
}
else if (bmp->Header.BitsPerPixel != 8)
{
BMP_LAST_ERROR_CODE = BMP_TYPE_MISMATCH;
}
else
{
*(bmp->Palette + index * 4 + 2) = r;
*(bmp->Palette + index * 4 + 1) = g;
*(bmp->Palette + index * 4 + 0) = b;
BMP_LAST_ERROR_CODE = BMP_OK;
}
}
BMP_STATUS BMP_GetError()
{
return BMP_LAST_ERROR_CODE;
}
const char* BMP_GetErrorDescription()
{
if (BMP_LAST_ERROR_CODE > 0 && BMP_LAST_ERROR_CODE < BMP