什么样的编程环境可以用来说明和测试算法未优化的空间复杂度？

Question

我可以用什么样的编程语言以及实现和编译器来研究任意算法的纯、非优化空间复杂度？我可以用什么方法来做到这一点？

例如，Scheme和Elixir实现尾调用优化。如果我编写的算法是递归的，那么无论我在堆栈上使用什么方法都可能显示出O(1)空间的复杂性。

另一个例子是，NodeJS实现垃圾收集。对于我在算法中初始化的任何数据结构，我都不知道它们是在堆栈上还是堆上分配的，因此调用process.memoryUsage()方法不允许我一致地进行基准测试。

如果我可以选择一个环境来分析算法的基线空间复杂性，那么我就可以将它与其他环境进行比较，从而选择合适的工作工具。

Answer 1

编程语言和实现并不存在于真空中。它们是各种优化的产物，在任何时候都可以在您不知道的情况下应用，如果它们不知道，那么您将处理一种天真的语言和实现，它们的性能无论如何都会低于最优。

换句话说，Scheme使用尾调用优化的事实是一个特性，而不是一个bug。作为空间复杂性的一部分，你必须考虑到这一点。如果您想知道没有TCO会是什么样子的话，那么您要么必须击败它(通过使递归调用不是尾调用)，要么使用自己的堆栈而不是语言的堆栈。

对于内存使用情况，我建议您只计算算法使用的对象数量，而不是尝试从操作系统获取原始内存使用情况。

不要忘记，不用运行程序就可以计算出Big。

Answer 2

最好的环境可能是纸和铅笔。

撇开这些不说，如果你想要在现实世界的硬件上展示不同的行为(但是在合成的，即非优化的等环境中)，即学术的话，那就去做一些

• 有足够的灵活性允许你的所有实验
• 易于编程(即支持更高层次的概念)
• 在编译/运行时对优化进行控制
• 保持测量干净，即不会带来不可预测的开销
• 提供测量内存/时间使用情况的功能。

在我的书中，C++符合要求。显然，它的功能非常广泛，它还提供了许多支持您的实验的库(不用自己来实现向量或哈希表)。大多数编译器都会允许您使用(几乎？)零优化。

例如，如果您正在查看Java，编写代码可能会更容易，但无法控制优化的级别。随机添加垃圾收集、JIT编译等，您就会意识到在解释度量时需要非常小心。

如果这样做是出于实际的原因，那么就在实际重要的平台上进行。在Windows机器上证明算法在C++中工作是没有意义的，而在运行特定浏览器的移动电话上，您的JavaScript库就会失败。