algorithm - "algorithm problem size"到底是什么意思？

Question

我目前在我的大学学习数据结构类(class)，并且在之前的类(class)中做过一些算法分析，但这是我在之前的类(class)中遇到的最困难的部分。我们现在将在我的数据结构类(class)中学习算法分析，因此我将回顾我上一门类(class)的教科书，看看它对这个问题的看法。

在教科书中，它说“对于我们要分析的每个算法，我们需要定义概率的大小-lem。”进行一些 Google 搜索后，并不完全清楚“问题大小”的实际含义。我正在尝试更具体地定义问题大小，以便我可以在算法中识别它。

我知道，如果我有一个对数字列表进行排序的算法，则问题大小为 n，即列表的大小。话虽如此，除了在那种情况下，这并不能说明“问题规模”到底是什么。算法不仅仅是对数字进行排序的过程，所以我不能总是说问题的大小就是列表中元素的数量。

希望外面有人能为我澄清事情，你们都做得很好。

谢谢

Answer 1

答案就在你引用的部分(强调我的):

For every algorithm we want to analyze, we need to define the size of the problem

“问题大小”仅在相对于算法的数值上定义。对于输入为数组或列表的算法，问题大小通常用其长度来衡量；对于图形算法，问题大小通常由顶点数和边数(有两个变量)来衡量；对于输入为单个数字的算法，问题大小可以通过数字本身来衡量，也可以通过二进制表示数字所需的位数来衡量，具体取决于上下文。

所以“问题大小”的含义是特定于算法解决的问题。如果您想要一个可以适用于所有问题的更通用的定义，那么问题大小可以定义为表示输入所需的位数；但这个定义并不实用，仅在理论上用于讨论问题的类别(例如在多项式时间内可解决的问题)。