БлогNot. Проверяем O большое для подпрограммы

Проверяем O большое для подпрограммы

Постановка задачи. Элементы целочисленных массивов а длиной 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, чтобы получить искомую зависимость времени работы алгоритма от количества обрабатываемых элементов. Вот соответствующий полный листинг, который можно вставить в пустой проект C++, код проверялся в актуальных сборках Visual Studio 2019, 2022:

#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();
 }
};

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;
}

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;
}

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++];
}

int main() {
 int n = 1000, m = 1000; //начальные размерности (не обязательно одинаковые)
 const int steps = 100; //количество циклов с увеличением размерности
 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 += 1000;
  m += 1000;
 }
 return 0;
}
Выделили и скопировали данные из консоли
Выделили и скопировали данные из консоли
Вставили их в текстовый файл, нажали Ctrl+H, заменили все точки на запятые, сохранили как 1.txt
Вставили их в текстовый файл, нажали Ctrl+H, заменили все точки на запятые, сохранили как 1.txt
Открыли текстовый файл в Excel
Открыли текстовый файл в Excel

Формат исходных данных выберем "фиксированной длины", кнопка "Далее", там проверим, что разделители столбцов определены верно:

Разделитель данных нашёл 2 столбца
Разделитель данных нашёл 2 столбца

и ещё раз нажмём "Далее", а затем "Готово".

Выделим все данные в столбцах A и B, нажмём Вставка, Диаграммы, Точечная с гладкими кривыми и маркерами, растянем диаграмму до удобного масштаба. Возможно, понадобится что-то подстроить, я щёлкнул правой кнопкой на последнем значении подписей горизонтальной оси, выбрал "Формат оси" и уточнил верхнюю границу по оси X:

Уточнение параметров диаграммы
Уточнение параметров диаграммы

Видно, что это в целом линейный характер зависимости времени выполнения алгоритма от размерности входных данных, не считая неизбежных "аномальных выбросов", которых при другом запуске может и не быть.

28.03.2023, 18:10 [232 просмотра]


теги: c++ программирование учебное графика алгоритм excel

К этой статье пока нет комментариев, Ваш будет первым