Временная сложность алгоритмов и алгоритмы сортировки на C++
Не доходят руки сформатировать несколько статеек, сделаем пока эту, актуальную в данный момент для учебных целей.
Функции и код из статьи проверялись в пустом консольном проекте актуальной сборки Visual Studio 2019 или 2022.
Что-то постарее и на PHP было здесь.
1. Временная сложность алгоритмов
Важнейшим показателем качества алгоритма является его эффективность.
Основные показатели эффективности - это время, необходимое для решения задачи и объём требуемой памяти. Алгоритм может прекрасно решать задачу, но при этом быть неэффективным.
Общее время выполнения программы зависит от двух факторов:
- времени выполнения каждого оператора;
- частоты выполнения каждого оператора.
Время выполнения каждого оператора зависит от среды выполнения, операционной системы и других системных характеристик, поэтому оценивается не быстродействие программы на конкретном компьютере, а обобщённая характеристика производительности алгоритма.
В информатике временная сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе.
Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также отбрасывает константные множители (коэффициенты). Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть, при стремлении размера входа к бесконечности.
Например, если существует число n0, такое, что время работы алгоритма для всех входов длины n > n0 не превосходит 5n3+3n, то временную сложность данного алгоритма можно асимптотически оценить как О(n3).
Временная сложность обычно оценивается путём подсчёта количества элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.
В зависимости от эффективности существует много типов алгоритмов, перечислим некоторые из них в порядке уменьшения эффективности.
Константный (1). Приложение выполняет фиксированное количество операций, которые, как правило, требуют постоянного времени. К этому типу алгоритмов относятся расчёты по любым готовым формулам.
Логарифмический (log N). Выполняется медленнее, чем программы с постоянным временем. Примером подобного алгоритма может служить алгоритм бинарного поиска.
Бинарный поиск (binary search) – алгоритм поиска элемента в упорядоченном списке. На каждой итерации происходит деление списка на две части, по этой причине алгоритм называют также методом деления пополам или дихотомии. Он эффективен, так как на каждой итерации количество элементов в рабочей области списка уменьшается вдвое.
Описание алгоритма бинарного поиска:
- определяем значение элемента в середине рабочей области списка данных и сравниваем его с искомым;
- если они равны, возвращаем элемент;
- если значение элемента в середине списка больше искомого, то поиск продолжается в левой от среднего элемента части списка, иначе в правой;
- проверяем не сошлись ли в одно значение границы рабочей области, если да - искомого значения нет, иначе возвращаемся на первый шаг.
Например, такой алгоритм является оптимальным при отгадывании целого числа из заданного диапазона значений (с ответами "моё число меньше" или "моё число больше"), при численном поиске минимума функции одной переменной и ещё для многих задач.
Линейный (N). Как правило, встречается там, где метод основан на цикле. К примеру, поиск наибольшего элемента в массиве или любая другая поэлементная обработка - типичные алгоритмы O(N).
Рост трудоемкости алгоритма для данного метода пропорционален размерности данных, поэтому его и называют линейным.
Линейно-логарифмический (N log N). Примерами подобных алгоритмов могут служить лучшие из алгоритмов сортировки, такие как быстрая сортировка и сортировка слиянием (см. п. 3).
Квадратичный (N2). Как правило, методы, которые соответствуют данному алгоритму, содержит два вложенных цикла - внешний и вложенный, которые выполняются для всех значений вплоть до размерности данных N. В качестве примера можно привести любую последовательную обработку всех элементов двумерной матрицы или же обработку элементов одномерного массива по принципу "каждый элемент взаимодействует с каждым".
Рассмотрим подробнее базовый алгоритм "наивной" (разновидность пузырьковой) сортировки, часто встречающийся в учебных задачах, для одномерного массива a, состоящего из n элементов. Требуется так переставить элементы, чтобы они образовывали неубывающую или невозрастающую последовательность.
В худшем случае нам придётся совершить обход N*N элементов с помощью двух вложенных циклов.
Откуда берётся эта оценка?
Первый элемент массива нам нужно сравнить во всеми остальными и при необходимости поменять два элемента местами:
сортировка массива из 5 элементов, циклы 1-2
сортировка массива из 5 элементов, циклы 3-4
Вот реализация данной сортировки на C++:
#include <iostream>
void print_array(int n, int a[]) {
for (int i = 0; i < n; i++) std::cout << a[i] << ' ';
std::cout << std::endl;
}
int main() {
const int n = 5;
int a[n] = { 5, 2, 3, 4 , 1};
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
int temp = a[i]; a[i] = a[j]; a[j] = temp;
print_array (n,a); //печатаем массив - только для наглядности
}
}
}
return 0;
}
Подобный принцип сравнения "каждый с каждым" используется при решении большого количества задач, но редко является экономичным способом решения.
Мы рассмотрели только некоторые виды сложностей алгоритмов, которых существует гораздо больше.
Вот схема, наглядно показывающая зависимость количества выполняемых операций от количества обрабатываемых элементов для алгоритмов различной временной сложности:
Зависимость количества операций от количества элементов для различных О большое
На следующем рисунке показано время выполнения алгоритма с определённой сложностью в зависимости от размера входных данных при выполнении одного миллиона операций в секунду:
Время выполнения алгоритма для различных О большое в зависимости от размера данных
Примечания.
1. В тексте дана "идеальная модель" сложности алгоритма. Подразумевается, что воздействие окружения (операционной системы) на выполнение программы пренебрежимо мало. В реальности, конечно, окружение привносит свой вклад в итоговую производительность приложения.
2. В большинстве случаев сложность алгоритма зависит от наличия циклов. Метод без цикла с простыми выражениями имеет сложность O(1), метод с одним циклом - уже О(N), что теоретически хуже, чем O(1). Однако в реальности наличие простых операторов даже без цикла может давать меньшую производительность. Многое зависит от конкретной логики программы.
3. Ещё один аспект, который может повлиять на выполнение программы - это кэширование. Использование кэширования позволяет повторно выполнить операцию быстрее. Тем самым время выполнения одной и той же операции может быть непостоянным.
Резюмируя, можно сказать, что если задача решается арифметически, её можно выполнить за константное время, то есть, за O(1). В этом случае, конечно, решение за O(N) весьма грубо и неэффективно - например, сумму элементов арифметической прогрессии можно искать, вычисляя и складывая все элементы (решение O(N)), а можно воспользоваться известной из арифметики формулой (решение O(1)).
Если "готовых формул" для решения нет, мы прибегаем к тому или иному перебору решений - от худшего случая брутфорсинга (метода "грубой силы", то есть, полного перебора), до применения эффективных оптимизирующих алгоритмов.
Моя старая шутка гласит, что решение любой задачи на ЭВМ можно свести к одному трёхшаговому алгоритму:
- включить ЭВМ;
- решить задачу;
- выключить ЭВМ.
На самом деле, по сути имеется всего два способа решения любой задачи на компьютере.
Во-первых, для решения может понадобиться полный перебор всех подмножеств множества или генерация подмножеств заданной мощности или полный просмотр массива данных для извлечения нужной информации. Так работает большинство алгоритмов отбора и извлечения данных, включая просмотр БД с помощью SQL-запросов, различного рода сортировки и перестановки, требующие сравнения по принципу "каждый с каждым" и т.п.
Во-вторых, приложив усилия, перебор можно сделать неполным, заботясь об отсечении заведомо лишних "неперспективных" конфигураций данных, вводя критерии оптимизации, позволяющие направленно отбирать варианты, используя метод ветвей и границ и т.п.
Ещё одна старая шутка: мой знакомый профессор за "рюмкой чая" выразил эту мысль гораздо короче: есть только перебор и недобор.
Если второй случай порождает целый букет дисциплин и подходов, связанных с оптимизацией - от математического программирования и численных методов до генетических самообучающихся алгоритмов и многокритериальной оценки релевантности текста запросу, то первый класс алгоритмов гораздо более компактен и изучен.
Как правило, за повышение эффективности алгоритма приходится платить дополнительным объёмом хранимой информации.
2. Методы разработки алгоритмов
Теперь перечислим основные методы разработки алгоритмов более детально.
Ключевым подходом в алгоритмизации является сведение сложной задачи к некоторой композиции более простых подзадач.
1. Разложение задачи в последовательность разнородных подзадач. В этом методе обычно выделяется относительно небольшое число подзадач, по сути мало похожих друг на друга. Результаты решения первой подзадачи становятся исходными данными для решения второй подзадачи и т.д.
2. Разложение задачи в последовательность однородных подзадач (повторение, цикл). Это частный случай предыдущего метода.
3. Сведение задачи к самой себе (рекурсия). Задача сводится к более простой (как в предыдущем п.). Но эта более простая задача имеет ту же формулировку, что и исходная, с той лишь разницей, что решаться она должна для более простых исходных данных.
4. Метод последовательных приближений. Сначала каким-либо образом ищется значение х0, достаточно близкое к решению исходной задачи P. Затем, решение задачи Р сводится к многократному решению задачи R - улучшения имеющегося приближённого решения. Метод предполагает, что каким-то образом может быть оценено «качество» решения (обычно это требуемая точность решения).
5. Решение обратной задачи. Иногда обратная задача, то есть задача, соответствующая функции f-1(Y)=X решается значительно более просто, чем исходная задача. Тогда имеющийся алгоритм решения обратной задачи R иногда можно использовать для построения алгоритма решения прямой задачи Р. Например, задачу вычисления корня k степени из x можно свести к решению обратной задачи – вычисления корня уравнения x = yk , где x задано, а найти нужно y.
6. Метод полного перебора. Рассмотрим задачу о рюкзаке. Даны целое неотрицательное число N и k чисел {n1, n2, ..., nk}; найти подмножество в {n1, n2, ..., nk} такое, что сумма этих чисел равна N, если такое подмножество существует.
7. Эвристические методы. Под эвристическими понимаются методы, правильность которых не доказана, однако практика их использования даёт положительные результаты. Построить контрпример, демонстрирующий ошибочность или неверность метода, не удается. Но не удается доказать математическими средствами и правильность метода.
3. Алгоритмы сортировки
Сортировка – это упорядочение элементов массива по возрастанию или убыванию (точнее, по неубыванию или невозрастанию).
В любых начальных курсах по программированию алгоритмам сортировки уделяется большое внимание, в связи как с их распространённостью на практике (весьма часто нам нужно упорядочить свои данные по определённому признаку), так и наглядностью, с которой эти алгоритмы дают представление о временной сложности.
Существуют десятки алгоритмов сортировки, среди которых нет абсолютно лучшего: разные алгоритмы оптимальны для разных наборов и типов данных. Самые популярные из них - пузырьковая сортировка, сортировка перемешиванием, сортировка расчёской, сортировка вставками, сортировка выбором, быстрая сортировка, пирамидальная сортировка и другие.
Одни алгоритмы просты в реализации и хорошо подходят для разъяснения принципов, другие — для работы с большими массивами данных, третьи оптимизированы по числу процессорных циклов, скорости, и так далее.
Во всех наших примерах мы рассмотрим сортировку по возрастанию целочисленного массива a длиной 10000 элементов, заполненного значениями 10000, 9999, ..., 1, то есть, возьмём наихудший из возможных случаев.
Для обмена местами двух элементов массива применим стандартный алгоритм std::swap.
Оценку времени работы алгоритмов вы выполните самостоятельно на практическом занятии.
Главная программа будет выглядеть так:
#include <iostream>
#include <iomanip>
#include <algorithm>
int main() {
const int n = 10000;
int a[n];
for (int i = 0; i < n; i++) a[i] = n - i;
//Вызов подпрограммы сортировки с аргументами n,a
for (int i = 0; i < n; i++) { //Контрольный вывод отсортированного массива
std::cout << std::setw(6) << a[i];
}
return 0;
}
Достаточно вставить вызов нужной функции вместо комментария "Вызов подпрограммы".
Рассмотрим основные алгоритмы сортировки.
Сортировка пузырьком — один из самых известных алгоритмов сортировки. Его суть в последовательном сравнении значений двух соседних элементов слева направо: если предыдущее больше последующего, они меняются местами. При сортировке элементов по убыванию, наоборот: в конец списка уходят элементы с наименьшим значением.
Здесь во внутреннем цикле перебираем значения, начиная с последнего (n-1), и в каждом следующем проходе уменьшаем количество просмотренных элементов (j > i).
void bubble_sort(const int n, int a[]) {
int i, j;
for (i = 0; i < n - 1; i++) { //внешний цикл отвечает за номер прохода
for (j = n - 1; j > i; j--) {
//внутренний - за перебор элементов в одном проходе
if (a[j - 1] > a[j]) std::swap (a[j - 1], a[j]);
}
}
}
Вызвать нашу функцию из main можно так:
bubble_sort(n, a);
Сложность алгоритма составляет О(n2).
Алгоритм хорошо себя показывает с большими наборами данных, где элементы почти отсортированы и требуется всего одна итерация, чтобы определить, отсортирован ли список до конца.
В случае с совершенно неотсортированным списком, для пузырьковой сортировки он должен быть хотя бы небольшим.
Улучшенными версиями пузырькового метода являются сортировки перемешиванием (шейкерная) и расчёской.
Сортировка вставками. Это простая сортировка, при которой массив постепенно перебирается слева направо. При этом элемент сравнивается со всеми предыдущими элементами и размещается так, чтобы оказаться в подходящем месте среди ранее упорядоченных элементов. Так происходит до тех пор, пока набор входных данных не будет исчерпан. Звучит сложно, но на деле это довольно простой алгоритм.
void inserting_sort(const int n, int a[]) {
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
for (j = i; j > 0 && temp < a[j - 1]; j--) {
a[j] = a[j - 1];
}
a[j] = temp;
}
}
Вызов функции аналогичен пузырьковой сортировке. Сложность алгоритма составляет О(n2).
Как и в случае с пузырьковой сортировкой, этот алгоритм работает быстрее всего на очень маленьком или почти отсортированном наборе данных.
Данный алгоритм также используется как часть алгоритма сортировки Шелла.
Сортировка выбором — это некий гибрид между пузырьковой сортировкой и вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее неотсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце.
void selection_sort(const int n, int a[]) {
int min, imin, i, j;
for (i = 0; i < n; i++) {
min = a[i]; imin = i;
for (j = i + 1; j < n; j++) {
if (a[j] < min) {
min = a[j]; imin = j;
}
}
std::swap (a[imin], a[i]);
}
}
Вызов функции аналогичен пузырьковой сортировке. Сложность алгоритма также соответствует О(n2).
Быстрая сортировка относится к эффективным алгоритмам и состоит из нескольких шагов:
1. Из массива выбирается опорный элемент, чаще всего посередине массива.
2. Другие элементы массива распределяются таким образом, чтобы меньшие размещались до него, а большие — после.
3. Далее первые шаги рекурсивно применяются к подмассивам, которые разделились опорным элементом на две части — слева и справа от него.
void quick_sort(const int n, int a[], int low, int high) {
if (n == 0 || low >= high) return;
//завершить, если массив пуст или уже нечего делить
int middle = low + (high - low) / 2;
int opora = a[middle]; //выбираем опорный элемент
int i = low, j = high; //разделяем на подмассивы
while (i <= j) {
while (a[i] < opora) i++;
while (a[j] > opora) j--;
if (i <= j) { //меняем местами
std::swap (a[i],a[j]);
i++;
j--;
}
}
if (low < j) { //рекурсия для сортировки левой и правой части
quick_sort(n, a, low, j);
}
if (high > i) {
quick_sort(n, a, i, high);
}
}
Так как алгоритм рекурсивен, в функцию дополнительно передаются аргументы low и high, хранящие индексы начала и конца текущего подмассива.
Соответственно, вызов подпрограммы будет иметь вид
quick_sort(n, a, 0, n - 1);
Сложность алгоритма: O(n log n) в среднем, O(n2) в худшем случае.
Быстрая сортировка очень популярна, но она далеко не всегда O(n log n), так как в худших случаях она становится O(n2).
Быстрая сортировка более эффективна для наборов данных, которые помещаются в доступную память. Для больших наборов она неэффективна, и в этом случае более предпочтительна, например, сортировка слиянием.
Быстрая сортировка — это сортировка на месте (т. е. она не требует дополнительной памяти), поэтому её целесообразно использовать для массивов.
Стандартный алгоритм C++ std::sort использует интроспективную сортировку, основанную на идеях алгоритма quick sort.
Сортировка Шелла. Алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными "грубыми" проходами.
void shell_sort(const int n, int a[]) {
for (int step = n / 2; step > 0; step /= 2) {
for (int i = step; i < n; i++) {
for (int j = i - step; j >= 0 && a[j] > a[j + step]; j -= step) {
if (a[j] > a[j + step]) std::swap(a[j],a[j+step]);
}
}
}
}
Вызов функции аналогичен первым трём сортировкам. Сложность алгоритма: О(n2) в худшем случае, O(n log2 n) в среднем.
Несмотря на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
- отсутствие потребности в памяти под стек;
- отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до О(n2), что случается чаще, чем худшее гарантированное время для сортировки Шелла.
Сортировка слиянием. Этот алгоритм упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа "разделяй и властвуй", то есть, хорошо подходит для распараллеливания на несколько процессоров. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
void merge(int a[], int const low, int const mid, int const hi) {
//Слияние подмассивов a[low..mid] и a[mid+1..hi]
//Эта функция нужна для работы merge_sort
const int n_low = mid - low + 1, n_hi = hi - mid;
//Создать временные массивы
int *a_left = new int[n_low], *a_right = new int[n_hi];
//Скопировать данные в них
for (int i = 0; i < n_low; i++) a_left[i] = a[low + i];
for (int j = 0; j < n_hi; j++) a_right[j] = a[mid + 1 + j];
int i_left = 0, i_right = 0; //Начальные индексы в подмассивах
int index = low; //Начальный индекс в массиве слияния
//Сливаем временные массивы в a[low..hi]
while (i_left < n_low && i_right < n_hi) {
if (a_left[i_left] <= a_right[i_right]) {
a[index] = a_left[i_left];
i_left++;
}
else {
a[index] = a_right[i_right];
i_right++;
}
index++;
}
//Копируем оставшиеся элементы
while (i_left < n_low) {
a[index] = a_left[i_left];
i_left++; index++;
}
while (i_right < n_hi) {
a[index] = a_right[i_right];
i_right++; index++;
}
delete[] a_left;
delete[] a_right;
}
void merge_sort(int a[], const int low, const int hi) {
if (low >= hi) return;
int mid = low + (hi - low) / 2;
merge_sort (a, low, mid);
merge_sort (a, mid + 1, hi);
merge(a, low, mid, hi);
}
Эта сортировка использует в качестве буфера дополнительный массив как минимум с таким же размером как у a и, подобно алгоритму быстрой сортировки, является рекурсивной, то есть, требует передачи ещё двух дополнительных аргументов, отвечающих за текущую длину сортируемой части. Поэтому вызов функции выглядит так:
merge_sort(a, 0, n-1);
Сложность алгоритма: O(n log n) и в худшем случае, и в среднем.
Алгоритм сортировки считается стабильным (см. столбец "Stable" в таблице Вики), если при сортировке записей по определённому столбцу или полю он всегда сохраняет относительный порядок элементов с одинаковым ключом, например, для исходного массива [0; 2; 0; 1], конечно, получится [0; 0; 1; 2], но первый из двух нулей в исходном массиве останется первым и в отсортированном.
В простейшем случае чтобы проверить алгоритм сортировки на стабильность можно руководствоваться следующим алгоритмом:
- создать список объектов, которые рандомизируются на основе их критерия сортировки;
- сохраняя тот же порядок объектов, добавить последовательный идентификатор к каждому объекту. Этот идентификатор не должен быть частью критериев сортировки;
- отсортировать объекты в порядке возрастания по выбранному критерию (столбцу).
Теперь можно просмотреть отсортированный массив или список и проверить только одинаковые элементы на предмет того, расположены ли их идентификаторы в порядке возрастания. Если да, то сортировка ведёт себя как стабильная, в противном случае - нет.
Следует понимать, что такое тестирование - необходимое, но не достаточное условие стабильности сортировки, поскольку продолжение стабильной сортировки не обязано быть стабильным в будущем. С другой стороны, один отрицательный тест достаточен для доказательства того, что сортировка нестабильна.
В современных версиях C++ есть стандартный алгоритм стабильной сортировки std::stable_sort.
4. Пример выполнения варианта задания
Общее задание может быть примерно таким: выполнить задачу своего варианта, реализовав в виде подпрограммы-функции алгоритм сортировки некоторых данных.
Обоснованно оценить временную сложность алгоритма.
Измерить время выполнения сортировки при меняющихся в достаточно широких пределах размерностях входных данных.
Построить график зависимости затраченного времени от количества обработанных элементов.
Постановка задачи. Элементы целочисленных массивов а длиной n и b длиной m упорядочены по неубыванию. Получить в массиве с все элементы массивов а и b. Массив с также должен быть упорядочен по неубыванию.
Подключим нужные заголовочные файлы и готовый класс Timer, который позволит нам измерить время выполнения алгоритма:
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <chrono>
#include <string>
class Timer {
std::chrono::high_resolution_clock::time_point start;
public:
Timer() {
start = std::chrono::high_resolution_clock::now();
}
double stop() {
std::chrono::high_resolution_clock::time_point end =
std::chrono::high_resolution_clock::now();
std::chrono::duration <double> time_span = std::chrono::duration_cast
<std::chrono::duration<double>>(end - start);
return time_span.count();
}
};
Для запуска таймера достаточно будет поместить в нужном месте программы строчку вида
Timer t;
а для остановки - строчку
double time = t.stop();
Между запуском и остановкой не должно быть никаких не относящихся к алгоритму действий, особенно вывода в консоль, иначе результаты измерения будут некорректными. Вывести полученное время (в секундах) можно затем оператором вида
std::cout << std::fixed << std::setw(15) << time << std::endl;
Так мои исходные массивы уже упорядочены, для генерации случайного массива a длиной n элементов, имеющих произвольный тип данных T, я применю следующую шаблонную функцию:
template <typename T> void fill_array(const int n, T a[], T low, T step) {
srand((unsigned int)time(NULL));
a[0] = low;
for (int i = 1; i < n; i++) a[i] = a[i-1] + rand() % step;
}
Аргумент low здесь означает значение первого элемента, а аргумент step - шаг, определяющий максимальную разницу между следующим элементом и предыдущим (разница будет принимать значения от 0 до step-1 включительно).
Если массивы данных не упорядочены, эту функцию можно заменить на
template <typename T> void fill_array(const int n, T a[], T low, T hi) {
srand((unsigned int)time(NULL));
for (int i = 0; i < n; i++)
a[i] = low + rand() % (hi - low + 1);
}
Здесь аргументы low и hi означают минимальное и максимальное допустимые значения генерируемых элементов массива.
Для вывода массива в консоль во всех случаях подойдёт шаблонная функция вида
template <typename T> void type_array(const int n, T a[],
std::string msg="", int w=5) {
std::cout << std::fixed;
if (msg.length() > 0) std::cout << std::setw(w) << msg;
for (int i = 0; i < n; i++)
std::cout << std::setw(w) << a[i];
std::cout << std::endl;
}
Её необязательный аргумент msg (заголовок), если он указан и не пуст, будет напечатан перед списком элементов массива, а необязательный аргумент w, по умолчанию равный 5, позволяет задать количество позиций в консоли, которые займёт один элемент массива.
Реализуем алгоритм решения задачи в виде ещё одной функции:
void merge_sorted_arrays(int n, int a[], int m, int b[], int c[]) {
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] < b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}
//Не забываем про "хвост", оставшийся в одном из массивов:
while (i < n) c[k++] = a[i++];
while (j < m) c[k++] = b[j++];
}
Идея очень проста - мы завели в каждом массиве свой счётчик элементов и увеличиваем их в зависимости от того, меньше значение a[i] значения b[j] или нет. Так как мы дойдём до конца одного из массивов раньше, чем закончатся элементы другого, учтём обработку "хвоста" после основного цикла.
Поскольку всего выполняется не более n+m шагов циклов, временная сложность алгоритма составляет O(n+m) или асимптотически O(n). Можно предположить, что улучшить её невозможно, так как каждый из массивов должен хотя бы один раз быть пройден от начала до конца.
Главная программа займётся организацией тестирования алгоритма. Последовательно увеличивая значения n и m, будем создавать на каждом шаге цикла тестирования новые динамические массивы a и b (и удалять их в конце шага), заполнять массивы числами и вызывать функцию merge_sorted_arrays, измеряя время её работы. Увеличив константу steps, мы сможем выполнить любое нужное нам количество тестов.
int main() {
int n = 10, m = 8; //начальные размерности (не обязательно одинаковые)
const int steps = 1; //количество циклов с увеличением размерности
for (int i = 0; i < steps; i++) {
int *a = new int [n];
int *b = new int [m];
int *c = new int [n+m];
if (!a || !b || !c) {
std::cout << "No memory for n = " << n;
return -1;
}
fill_array <int> (n, a, -n, 5);
fill_array <int> (m, b, -m, 5);
type_array <int> (n, a, "A=", 8);
type_array <int> (m, b, "B=", 8);
Timer t;
merge_sorted_arrays (n,a,m,b,c);
double time = t.stop();
type_array <int>(n+m, c, "C=", 8);
std::cout.precision(12);
std::cout << std::fixed << std::setw(8) << (n+m) <<
std::setw(15) << time << std::endl; //вывод размерности и времени
delete[] c;
delete[] b;
delete[] a;
n += 100;
m += 100;
}
return 0;
}
Убедившись в правильности работы алгоритма при steps = 1 и небольших значениях n, m, можно увеличить steps, закомментировать строчки с вызовом функции type_array, чтобы получить искомую зависимость времени работы алгоритма от количества обрабатываемых элементов. Вот график, построенный в Excel для n+m = 2000, 4000, ..., 200000 при значении steps = 100:
результаты измерения временной сложности алгоритма
Видно, что линейный характер зависимости времени выполнения алгоритма от размерности входных данных в целом сохраняется.
23.12.2023, 15:35 [863 просмотра]