Как проверить пространственную сложность алгоритмов сортировки?

Question

Если бы мне пришлось реализовать три алгоритма сортировки в c ++, а затем я хотел бы изучить сложность их пространства / объем ОЗУ, которое они занимают.Как я мог это сделать?Существуют ли стандартные или сторонние библиотеки, которые я могу использовать?

Answer 1

Это под Unix / Linux?Если это так, вы можете вычислить разницу между значениями, возвращаемыми sbrk (0) в начале и в конце вашей программы.Это даст общий объем памяти кучи во время выполнения.

См. Страницу руководства в sbrk (2)." Вызов sbrk () с шагом 0 может использоваться для определения текущего местоположения остановки программы. "

(приложение) Использование игрушечной программы C ++, которая просто выделяет один большой векторполучается, что среда выполнения GNU C ++ имеет тенденцию выделять очень большие объекты с помощью mmap (), а не sbrk ().

Использование strace:

$ strace ./vec1.x |& grep map
...
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f4ac2b42000
mmap(NULL, 800002048, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f4a93051000
...
$

Вы также можете выполнить grep с помощью brk вместо map .

Использование Valgrind:

$ valgrind ./sbrk1.x
...
==22223==   total heap usage: 3 allocs, 3 frees, 800,073,728 bytes allocated
....
$

Надеюсь, это поможет!

Answer 2

Если вы хотите проверить их сложность - как асимптотическую функцию - вы не сможете сделать это эмпирически, например, путем перехвата распределения и отмены распределения Вам нужно будет вывести асимптотические ограничения на максимальный объем выделенного пространства, тщательно проанализировав свой код. Теоретически невозможно автоматизировать эту задачу в общем случае, поскольку ваша программа может быть сколь угодно сложной.

На практике то, что я предлагаю вам, это попытаться организовать ваши распределения и перераспределения так, чтобы они не происходили спонтанно повсюду. Это должно помочь вам ограничить максимально выделенную сумму.

В той степени, в которой вы запрашиваете программный инструмент для измерения выделенной суммы во время прогона - это не по теме для StackOverflow, и вы должны спросить об этом на softwarerecs.stackexchange.com.