c++ - 如何考察排序算法的空间复杂度？

Question

如果我要在 C++ 中实现三种排序算法，然后想检查它们的空间复杂度/它们占用的 RAM 量。我怎么能这样做？我可以使用任何标准库或第三方库吗？

Answer 1

这是在 Unix/Linux 下吗？如果是这样，您可以计算程序开始和结束时 sbrk(0) 返回的值之间的差异。这将给出运行期间堆内存的总量。

请参阅 sbrk(2) 的手册页。"以 0 为增量调用 sbrk() 可用于查找程序中断的当前位置。"

(附录)使用仅分配一个大 vector 的玩具 C++ 程序，事实证明 GNU C++ 运行时倾向于使用 mmap() 而不是 sbrk() 分配非常大的对象。

使用跟踪:

$ 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
...
$

您也可以使用 brk 而不是 map 进行 grep。

使用 Valgrind:

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

希望对您有所帮助!