Необходимо помнить пару моментов: в первую очередь, при изменении размеров аппаратное обеспечение (по крайней мере, на обычном компьютере) также будет оказывать влияние. В частности, когда ваши данные становятся слишком большими, чтобы поместиться в определенный размер кэша, вы можете ожидать существенного скачка во времени выполнения, который полностью не зависит от рассматриваемого алгоритма.
Чтобы получить хорошее представление о самом алгоритме, вы должны (вероятно) начать со сравнения с каким-то алгоритмом с действительно очевидной сложностью, но работающим с тем же размером данных. Для одной очевидной возможности, время, сколько требуется, чтобы заполнить ваш массив случайными числами. По крайней мере, если предположить достаточно типичный PRNG, он, безусловно, должен быть линейным.
Затем оцените ваш алгоритм и посмотрите, как он относительно меняется на линейный алгоритм для тех же размеров. Например, вы можете использовать такой код:
#include <vector>
#include <algorithm>
#include <iostream>
#include <time.h>
#include <string>
#include <iomanip>
class timer {
clock_t begin;
std::ostream &os;
std::string d;
public:
timer(std::string const &delim = "\n", std::ostream &rep=std::cout)
: os(rep), begin(clock()), d(delim)
{}
~timer() { os << double(clock()-begin)/CLOCKS_PER_SEC << d; }
};
int main() {
static const unsigned int meg = 1024 * 1024;
std::cout << std::setw(10) << "Size" << "\tfill\tsort\n";
for (unsigned size=10000; size <512*meg; size *= 2) {
std::vector<int> numbers(size);
std::cout << std::setw(10) << size << "\t";
{
timer fill_time("\t");
std::fill_n(numbers.begin(), size, 0);
for (int i=0; i<size; i++)
numbers[i] = rand();
}
{
timer sort_time;
std::sort(numbers.begin(), numbers.end());
}
}
return 0;
}
Если я нарисую время и время для сортировки, я получу что-то вроде этого:
Поскольку наши размеры экспоненциальные, наш линейный алгоритм показывает (приблизительно) экспоненциальную кривую. Время сортировки, очевидно, все еще увеличивается (несколько) быстрее.
Редактировать: Справедливости ради, я, вероятно, должен добавить, что log (N) растет настолько медленно, что почти для любого практического объема данных он вносит очень небольшой вклад. Для большинства практических целей вы можете просто считать быструю сортировку (например) линейной по размеру, просто с несколько большим постоянным коэффициентом, чем заполнение памяти. Линейное увеличение размера и отображение результатов делает это более очевидным:
Если вы посмотрите внимательно, вы можете увидеть верхнюю линию, показывающую только небольшую восходящую кривую от коэффициента «log (N)». С другой стороны, я не уверен, что вообще заметил бы искривление, если бы не знал, что оно должно .