Строим зависимость количества шагов сортировки от размерности массива
Сортировки - одна из самых классических задач, имеющих широчайшую сферу применения.
Давайте сравним пару распространённых алгоритмов сортировки не по времени выполнения, как в этом скрипте на PHP, а по количеству шагов цикла, выполняемому алгоритмом. Фактически, это будет прямо коррелировать с временной сложностью.
Возьмём один из "базовых" алгоритмов (подойдут линейная сортировка выбором или сортировка "пузырьком", имеющие одинаковую вычислительную сложность) и один из "продвинутых", скажем, популярную быструю сортировку.
Меняя размерность массива от 100 до 10000, будем генерировать вектор случайных целочисленных значений, снимать с него копию и выполнять сортировки. Ниже показана программа на C++, проверенная в консоли Visual Studio 2019.
#include <iostream> #include <iomanip> #include <string> #include <vector> #include <algorithm> #include <cstdlib> using namespace std; struct RandomGenerator { //функтор для генерации случайных чисел int maxValue; RandomGenerator(int max) : maxValue(max) {} int operator()() { return rand() % maxValue; } }; template <class T> int linear (vector <T> &a) { //Линейная (отбором) T v; int n = a.size(),s=0,i,j; for (i = 0; i < n - 1; i++) for (j = i + 1; j < n; j++) { s++; if (a[i] > a[j]) { v=a[i]; a[i] = a[j]; a[j] = v; } } return s; } template <class T> int bubble (vector <T> &a) { //Метод пузырька, то же количество шагов, что у linear, можно использовать вместо неё T v; int n = a.size(), s = 0, i, j; for (i = 1; i < n; i++) for (j = n - 1; j >= i; j--) { s++; if (a[j-1] > a[j]) { v = a[j-1]; a[j-1] = a[j]; a[j] = v; } } return s; } template <class T> int partition (vector <T> &a, int left, int right, int &s) { //Выбор номера элемента для quick int val = a[left + (right - left) / 2]; int i = left, j = right; T temp; while (i <= j) { while (a[i] < val) { i++; s++; } while (a[j] > val) { j--; s++; } s++; if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } return i; } template <class T> int quick (vector <T> &a, int left, int right, int &s) { //Быстрая (с разделением) if (left < right) { int baseIndex = partition(a, left, right, s); quick(a, left, baseIndex - 1, s); quick(a, baseIndex, right, s); } return s; } template <class T> void print(string hdr, vector <T> &arr) { cout << hdr << ": "; for (T val : arr) cout << val << " "; cout << endl; } int main() { const int size = 10000; //максимальная размерность теста, кратна 100 for (int n = 100; n<=size; n+=100) { vector <int> arr1(n), arr2(n); generate (arr1.begin(), arr1.end(), RandomGenerator(n)); //сгенерировать случайный вектор //print ("arr1",arr1); double s1 = 0, s2 = 0; //среднее количество шагов цикла сортировки за steps попыток int c; const int steps = 10; for (int i = 0; i < steps; i++) { random_shuffle(arr1.begin(), arr1.end()); //перемешать copy (arr1.begin(), arr1.end(), arr2.begin()); //сделать копию элементов s1 += linear (arr1); //print ("arr1",arr1); c = 0; s2 += quick (arr2,0,n-1,c); //print ("arr2", arr2); } cout.precision(2); cout << setw(15) << fixed << (n) << setw(15) << fixed << (s1 / steps) << setw(15) << fixed << (s2 / steps) << endl; } cin.get(); return 0; }
Полученные результаты и графики есть в приложенном документе Excel (2007 и выше). Видно, что у QuickSort количество операций растёт линейно в зависимости от размерности массива.
Следует иметь в виду, что контейнеры STL (как, впрочем, и строки std::string
) имеют свойство сами "баловаться" с оперативкой, плюс
контейнеры в любом случае выделяют память, необходимую для хранения объектов, в "куче" (динамически распредялемой области памяти),
поэтому vector <T> *myvec = new vector <T> ()
вместо vector <T> myvec
смысла не имеет.
Ну и вообще любое массовое динамическое выделение памяти существенно замедляет выполнение программы, особенно неявное выделение памяти через new
:)
15.02.2020, 15:11 [1382 просмотра]