На бирже курсовых и дипломных проектов можно найти готовые бесплатные и платные работы или заказать написание уникальных курсовых работ, дипломов, лабораторных работ, контрольных работ, диссертаций, рефератов по самым низким ценам. Добавив заявку на написание требуемой для вас работы, вы узнаете реальную стоимость ее выполнения.

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Быстрая помощь студентам

 

Работа № 100166


Наименование:


Лабораторка АНАЛИЗ ВРЕМЕННОЙ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ. Дана целочисленная квадратная матрица. Найти сумму модулей элементов, расположенных выше главной диагонали.

Информация:

Тип работы: Лабораторка. Предмет: Программирование. Добавлен: 03.11.2016. Сдан: 2015. Страниц: 5. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Лабораторная работа №1

АНАЛИЗ ВРЕМЕННОЙ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ

Цель работы: изучение средств анализа временной эффективности алгоритмов.

Задание

Разработать алгоритм и программу по индивидуальному заданию.

Провести математический анализ эффективности алгоритма и определить класс эффективности.

Провести эмпирический анализ производительности алгоритма и определить класс эффективности.

Индивидуальное задание


Дана целочисленная квадратная матрица. Найти сумму модулей элементов, расположенных выше главной диагонали.


Листинг программы

#include
#include
#include
#include

using namespace std;

int main()

{

srand(time(NULL));
int n = 0;
int sum = 0;

clock_t start, end;
float t = 0;

cin>>n; //Считываем с клавиатуры размер массива

int **a = new int* [n]; //Создаем массив указателей

for (int i = 0; i
{
a[i] = new int [n]; //Создаем элементы

}

//Генерируем случайным образом элементы матрицы и выводим на экран
for(int i=0; i
{
for(int j=0; j{

a[i][j] = rand()%99;
cout<}
cout<}

//Сложение элементов матрицы
start = clock();
for(int i=0; i{

for(int j=i+1; j
{
sum += abs(a[i][j]);
}
}

end = clock();

t = (end - start)/CLK_TCK;

//Вывод результата на экран
cout << "sum = " << sum <cout << "time = " << t <
//Удаление массива
for(int i=0; i
{
delete[]a[i]; //Удаляем каждый элемент
}

delete [] a; //Удаляем массив return 0;

}


?
СКРИНШОТ





Эмпирический анализ эффективности алгоритма
Получена следующая информация о количестве входных данных и соответствующем времени работы данного алгоритма, представленная в виде таблицы.
Для получения среднего времени работы алгоритма, для каждого значения N расчеты проводились 100000 раз. Для этого был введен цикл с параметром К
for (int k=0; k<100000;k++)
{sum=0;
for(int i=0; i{
for(int j=i+1; j{
sum += abs( a[i][j]);
}
}
}


N 10 20 40 80 160
t ( n) 32 96 368 1424 7562
(t(2 n) )/t(n) 96/32=3 368/96=3.83 1424/368=3.86 7562/1424=5.310

Т.е. при удвоении размера входных данных, время выполнения алгоритма растет в 4 раза. Квадратичная зависимость.



Рисунок 1 – График зависимости времени выполнения алгоритма от размера входных данных


Математический анализ алгоритма

Параметр, по которому оценивается размер входных данных: матрица размером n x n.
Основная операция алгоритма: суммирование элементов матрицы.
Зависимость числа выполняемых операций: от количества входных данных.

Сумма основных операций алгоритма:


С(n)=?_(i=0)^(n-1)-?_(j=i+1)^(n-1)-1=?_(i=0)^(n-1)-?(n-1-i-1)?=n(n-2)-?_(i=0)^(n-1)-i=n^2-2n-(n-1)/2=n^2-2,5n+0,5
В каждой строке матрицы, суммируются элементы, которые расположены "дальше" главной диагонали, т.е. те элементы, у которых номер столбца больше номера строки.
Квадратичная зависимость.




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


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы