"fixed dimension" 的计算复杂度
Computational complexity with "fixed dimension"
有一次我读了一篇科学论文：
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) 解决方案，请参见连接的 post：
Algorithm complexity with input is fix-sized
我的问题是，您是否认为这是多项式复杂度的有效论证？真的可以固定一维和输入数据并声称多项式复杂度吗？
大学时代的快速回忆。
Big-O 表示法只是算法执行方式的 UPPER 界限。
在数学上，f(x) 是 O(g(x)) 意味着存在常数 k>0 和 x0 使得
f(x) <= kg(x) 对于所有 x>x0
要回答你的问题，你不能修正自变量N。
如果你固定 N，说 <100，我们一定可以到达 O(1)，
因为根据定义。我们可以设置一个大的 K 来确保 f(N) <= kG(N) for all x (<100)
是的，这是一个合理的做法。
这真的取决于最初的问题，但在大多数情况下我会说固定维数是合理的。我希望这篇论文会声明类似 "polynomial complexity for practical purposes" 或类似的内容，或者提出一些论据来说明为什么限制 d 是合理的。
您可以与复杂度为 O(d^N) 的解决方案进行比较，其中固定维数并不意味着该解决方案是多项式的。因此当 d 较小时，呈现的显然更好。
这仅适用于某些算法。我不清楚 "dimension" 在某些情况下应该是什么。
例如SubSetSum 是 NP 完全的，因此没有多项式复杂度已知的算法。但输入只是 N 个数字。您也可以将其视为位长为 d 的 N 个数。但该算法仍然具有多项式复杂度。
同样适用于格的最短向量问题 (SVP)。输入是 N x N Basis（可以说是整数条目），您寻找最短的非零向量。这也是一个难题，目前还没有多项式复杂度的算法。
对于许多问题来说，使问题变得困难的不仅仅是输入数据的大小，还有该数据的某些属性或参数。例如。许多图形问题的复杂性分别以节点和边的数量给出。
有时，这些参数之间的差异可能会很大，例如，如果你有类似 O(n^d) 的东西，当 n 增长时复杂度只是多项式，但当 d 增长时是指数级的。
如果你现在碰巧有一个应用程序，你知道某个参数的值比如维度总是相同的或者有一个（小的）最大值，那么将这个参数视为固定的可以给你有用里面。所以像这样的陈述在科学论文中很常见。
但是，您不能只固定任何参数，例如您的内存是有限的，因此数据排序是恒定时间，因为该参数的界限太大，以至于将其视为固定不会给您任何有用的见解。
因此，固定所有参数通常不是一种选择，因为必须有一个方面使数据大小发生变化。如果您的复杂性增长非常缓慢，这可能是一个选择。
例如如果常量也非常小，则具有 O(log n) 操作的数据结构有时被认为具有有效的常量复杂度。或数据结构如联合查找结构，其中操作的分摊复杂度为 O(α(n))，其中 α 是阿克曼函数的反函数，该函数增长如此缓慢以至于不可能超过 10 或任何大小 n 任何可以想象的硬件都可以处理。
有一次我读了一篇科学论文：
The computational complexity of the algorithm is
O(N^d), whereNis the number of data,dis the dimension. Hence with fixed dimension, the algorithm complexity is polynomial.
现在，这让我想到，（如果我没记错的话）大 O 表示法是在二进制输入的数量中定义的。因此，如果我固定数据的维数，很自然地得出多项式解。此外，如果我也修复 N，输入的数量，我会得到一个 O(1) 解决方案，请参见连接的 post：
Algorithm complexity with input is fix-sized
我的问题是，您是否认为这是多项式复杂度的有效论证？真的可以固定一维和输入数据并声称多项式复杂度吗？
大学时代的快速回忆。 Big-O 表示法只是算法执行方式的 UPPER 界限。 在数学上，f(x) 是 O(g(x)) 意味着存在常数 k>0 和 x0 使得
f(x) <= kg(x) 对于所有 x>x0
要回答你的问题，你不能修正自变量N。 如果你固定 N，说 <100，我们一定可以到达 O(1)， 因为根据定义。我们可以设置一个大的 K 来确保 f(N) <= kG(N) for all x (<100)
是的，这是一个合理的做法。
这真的取决于最初的问题，但在大多数情况下我会说固定维数是合理的。我希望这篇论文会声明类似 "polynomial complexity for practical purposes" 或类似的内容，或者提出一些论据来说明为什么限制 d 是合理的。
您可以与复杂度为 O(d^N) 的解决方案进行比较，其中固定维数并不意味着该解决方案是多项式的。因此当 d 较小时，呈现的显然更好。
这仅适用于某些算法。我不清楚 "dimension" 在某些情况下应该是什么。
例如SubSetSum 是 NP 完全的，因此没有多项式复杂度已知的算法。但输入只是 N 个数字。您也可以将其视为位长为 d 的 N 个数。但该算法仍然具有多项式复杂度。
同样适用于格的最短向量问题 (SVP)。输入是 N x N Basis（可以说是整数条目），您寻找最短的非零向量。这也是一个难题，目前还没有多项式复杂度的算法。
对于许多问题来说，使问题变得困难的不仅仅是输入数据的大小，还有该数据的某些属性或参数。例如。许多图形问题的复杂性分别以节点和边的数量给出。
有时，这些参数之间的差异可能会很大，例如，如果你有类似 O(n^d) 的东西，当 n 增长时复杂度只是多项式，但当 d 增长时是指数级的。
如果你现在碰巧有一个应用程序，你知道某个参数的值比如维度总是相同的或者有一个（小的）最大值，那么将这个参数视为固定的可以给你有用里面。所以像这样的陈述在科学论文中很常见。
但是，您不能只固定任何参数，例如您的内存是有限的，因此数据排序是恒定时间，因为该参数的界限太大，以至于将其视为固定不会给您任何有用的见解。
因此，固定所有参数通常不是一种选择，因为必须有一个方面使数据大小发生变化。如果您的复杂性增长非常缓慢，这可能是一个选择。
例如如果常量也非常小，则具有 O(log n) 操作的数据结构有时被认为具有有效的常量复杂度。或数据结构如联合查找结构，其中操作的分摊复杂度为 O(α(n))，其中 α 是阿克曼函数的反函数，该函数增长如此缓慢以至于不可能超过 10 或任何大小 n 任何可以想象的硬件都可以处理。