algorithm - "fixed dimension"的计算复杂度

Question

有一次我读了一篇科学论文:

The computational complexity of the algorithm is O(N^d), where N is the number of data, d is the dimension. Hence with fixed dimension, the algorithm complexity is polynomial.

现在，这让我想到，(如果我没记错的话)大 O 符号是在二进制输入的数量中定义的。因此，如果我固定数据的维数，很自然地得出多项式解。此外，如果我还修复输入的数量 N，我将得到一个 O(1) 解决方案，请参阅相关帖子: Algorithm complexity with input is fix-sized

我的问题是，您是否认为这是多项式复杂性的有效论证？真的可以固定一维和输入数据并声称多项式复杂度吗？

Answer 1

是的，这是一件合理的事情。

这实际上取决于最初的问题，但在大多数情况下，我会说固定维数是合理的。我希望这篇论文声称诸如“用于实际目的的多项式复杂性”之类的东西，或者提出一些论据来说明为什么限制 d 是合理的。

您可以与复杂度为 O(d^N) 的解决方案进行比较，其中固定维数并不意味着该解决方案是多项式的。因此，当 d 较小时，所提供的显然更好。