Сортировка посредством выбора
1. находим номер минимального значения в текущем списке
2. производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)
3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
4. Покажем, почему данная реализация является неустойчивой.
Рассмотрим следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю.
Массив до сортировки:
{ (2, a), (2, b), (1, a) }
Уже после первой итерации внешнего цикла будем иметь отсортированную последовательность:
{ (1, a), (2, b), (2, a) }
Теперь заметим, что взаимное расположение элементов (2, a) и (2, b) изменилось. Таким образом, рассматриваемая реализация является неустойчивой.
5.
Так как после каждого прохода по внутреннему циклу делается только один обмен, то общее число обменов равно N-1, что в N/2 раз меньше, чем в сортировке пузырьком.
Число проходов по внутреннему циклу равно N-1 даже в случае сортировки частично или полностью отсортированного массива.
Сортировка Хоара
Быстрая сортировка относится к алгоритмам «разделяй и властвуй».
Алгоритм состоит из трёх шагов:
1. Выбрать элемент из массива. Назовём его опорным.
2. Разбиение: перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные после.
3. Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.
|
|
|
Сортировка Шелла
Сортируем вставкой подгруппы элементов, но только в подгруппе они идут не в ряд, а равномерно выбираются с некоторой дельтой по индексу. Методично уменьшая расстояние между элементами этих несвязных подмножеств, мы сортируем уже намного быстрее.
Временная сложность у «шелла» – достаточно сложный вопрос. Дело в том, что до сих пор нет строгой формулы, по которой строится оптимальный числовой ряд изменяющихся расстояний между элементами в подгруппах. Последовательность строится эмпирически, на основании многочисленных тестов с различными входными данными и последнее наилучшее уточнение для вышеупомянутых «дельт» было определено в 2001 году:
1, 4, 10, 23, 57, 132, 301, 701.
Контрольные вопросы:
1. Как оценивается сложность алгоритма?
Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.
|
|
|
2. Что называют временной сложностью алгоритма?
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные [1]. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, т.е. при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения работы, для всех входов длины n не превосходит 5n3 + 3n для некоторого n (большего некоторого n0), асимптотическая временная сложность равна O (n3).
Временная сложность зачастую оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом, где элементарная операция занимает для выполнения фиксированное время. Тогда полное время выполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель.
3. Что подразумевают под объемом-сложностью алгоритма?
|
|
|
Объемная сложность программы становится критической, когда объем обрабатываемых данных оказывается на пределе объема оперативной памяти ЭВМ. На современных компьютерах острота этой проблемы снижается благодаря как росту объема ОЗУ, так и эффективному использованию многоуровневой системы запоминающих устройств. Программе оказывается доступной очень большая, практически неограниченная область памяти (виртуальная память). Недостаток основной памяти приводит лишь к некоторому замедлению работы из-за обменов с диском. Используются приемы, позволяющие минимизировать потери времени при таком обмене. Это использование кэш-памяти и аппаратного просмотра команд программы на требуемое число ходов вперед, что позволяет заблаговременно переносить с диска в основную память нужные значения. Исходя из сказанного можно заключить, что минимизация емкостной сложности не является первоочередной задачей.
4. Каким образом оценивается временная сложность алгоритма?
Параметр временной сложности становится особенно важным для задач, предусматривающих интерактивный режим работы программы, или для задач управления в режиме реального времени. Часто программисту, составляющему программу управления каким-нибудь техническим устройством, приходится искать компромисс между точностью вычислений и временем работы программы. Как правило, повышение точности ведет к увеличению времени.
|
|
|
Практическая работа №3
«Определение сложности алгоритмов»
Цель работы: Научиться оценивать сложность алгоритмов
Задания для практического занятия:
1. Какая из функций растет быстрее?
Варианты ответов: A f = 
, B f = 
, C f = 
.
1. n − 100 n – 200 C
2. 
B
3. 
n + 
B
4. 
C
5. 
C
6. 
B
7. 
B
8. 
B
9. 
B
2. Составьте программу для решения следующих задач. Значения вводятся с клавиатуры. Выполнять проверку области определения и области значения, пороговых значений, деления на 0.
1. а) Даны два числа: вычислить их среднее арифметическое, их среднее геометрическое.
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int a,b;
cin >>a >>b;
cout <<"Sr. arifm: " <<(a+b)/2.0 <<endl
<<"Sr. geometr: " <<pow((a*b),0.5);
cin >> b;
cin >> b;
return 0;
}
б) Даны основание и высота равнобедренной трапеции, найти периметр.
#include <stdlib.h>
#include <iostream>
#include <conio.h>
#include <math.h>
#include <cmath>
using namespace std;
int main()
{
double a, b, c, d, p, h;
cout << "vvedite razmer nizhnego osnovaniya (v cm)";
cin >> a;
cout << "vvedite razmer verhnego osnovaniya (v cm)";
cin >> b;
cout << "vvedite razmer visoty (v cm)";
cin >> h;
d = abs(a - b) / 2;
c = sqrt(h*h + d*d);
p = 2 * c + a + b;
cout << "perimetr raven:" << " " << p << endl;
cin >> h;
return 0;
}
3. а) Составить программу решения линейного уровнения ax + b = 0.
#include <iostream>
using namespace std;
int main (int argc, char *argv[]){
float a, b;
cout<< "Vvedite znachenie a, b";
cin >> a >> b;
if(a)
cout << "x equals " << b/a << endl;
cin >> a;
return 0;
}
б) Даны координаты двух точек на плоскости. Составить программу, вычисляющую расстояния между ними.
#include <iostream>
#include <cmath>
using namespace std;
double length( int x1, int y1, int x2, int y2 )
{
return sqrt( (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) );
}
int main()
{
int x1, x2, y1, y2;
cout << "vvedite koordinati dvuh tochek ";
cin >> x1 >> y1 >> x2 >> y2;
cout << length( x1, x2, y1, y2 );
cin >> x1;
return 0;
}
3. а) Дано двухзначное число. Определить: число десятков, число единиц, сумму и произведение цифр.
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int n ;
cin>>n;
if(n>=10 && n<=99)
{
cout << "desyatki: " << n / 10 << "\nedinici: " << n % 10 << "\nsumma: " << n / 10 + n % 10 << "\n";
}
cin>>n;
}
б) Треугольник задан координатами трех вершин. Найти длины сторон и периметр.
#include <iostream.h>
#include <math.h>
int main()
{ int x1,x2,x3,y1,y2,y3;
float s,p,pp,a,b,c:
cout<<"x1="; cin>>x1;
cout<<"y1="; cin>>y1;
cout<<"x2="; cin>>x2;
cout<<"y2="; cin>>y2;
cout<<"x3="; cin>>x3;
cout<<"y3="; cin>>y3;
a = sqrt(((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2))); cout<<" a=" <<a<<endl ;
b = sqrt(((x1-x3)*(x1-x3))+((y1-y3)*(y1-y3))); cout<<" b=" <<b<<endl ;
c = sqrt(((x2-x3)*(x2-x3))+((y2-y3)*(y2-y3))); cout<<" c=" <<c<<endl ;
p = a+b+c;
cout<<"p=" <<p<<endl;
pp=p/2:
s=sqrt(pp*(pp-a)*(pp- b )*(pp-c));
cout<<"s=" <<s<<endl;
cin >> x1;
}
4. а) Даны катеты прямоугольного треугольника. Найти гипотенузу.
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
int main()
{
double a, b, c, d;
printf ("\nVvedite 1 katet a =");
scanf ("%u", &a);
printf ("\nVvedite 1 katet b =");
scanf ("%u", &b);
c=sqrt(a * a + b * b);
d=(a+b)/2;
printf ("\nPerimetr = %u", c);
printf ("\nPloshad = %u", d);
cin >> b;
}
б) Дано трехзначное число. Определить: число сотен, десятков, единиц, сумму и произведение его цифр.
#include <iostream>
using namespace std;
int main() {
int chislo;
cin >> chislo;
int soten = chislo / 100;
chislo = chislo % 100;
cout << " soten: " << soten;
int desyatkov = chislo / 10;
chislo = chislo % 10;
cout << " desyatkov: " << desyatkov;
int edinic = chislo;
cout << " edenic: " << edinic << endl;
int summa_cifr = soten + desyatkov + edinic;
cout << " summa cifr: " << summa_cifr << endl;
int pr_cifr = soten * desyatkov * edinic;
cout << "proizvedenie cifr: " << pr_cifr << endl;
cin >> chislo;
return 0;
}
Контрольные вопросы:
1. Что является оценкой качества алгоритма?
Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
2. Что называют верхней оценкой?
Записывается как 
(“О-большое от эн-квадрат”).
Таким образом, мы получили верхнюю оценку, т.е. количество операций (от которого прямо пропорционально зависит время работы) растет не быстрее, чем квадрат количества входных элементов.
Практическая работа № 4
Дата добавления: 2021-12-10; просмотров: 62; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!