我目前在我大学的“数据结构”课程中学习,并且在上一堂课上做了一些算法分析,但这是我上一堂课中最难熬的部分。现在,我们将在数据结构课程中进行算法分析,因此,我将回顾上一课程中的教科书,以了解问题的内容。
在教科书中说:“对于我们要分析的每种算法,我们都需要定义问题的大小。” 在做一些Google搜索时,尚不清楚“问题大小”的实际含义。我正在尝试对问题的大小进行更具体的定义,以便可以在算法中进行识别。
我知道,如果我有一种对数字列表进行排序的算法,则问题的大小为n,即列表的大小。话虽如此,但这并不能说明实际上是什么“问题大小”,除了在这种情况下。算法不仅是对数字进行排序的过程,所以我不能总是说问题的大小就是列表中元素的数量。
希望有人在那里可以为我澄清一些事情,而且你们所有人都过得很好。
谢谢
答案就在您引用的部分中(强调我的意思):
对于我们要分析的每种算法,我们需要定义问题的大小
“问题大小”仅相对于算法以数字方式定义。对于输入是数组或列表的算法,问题大小通常由其长度来衡量;对于图算法,问题大小通常由顶点数和边数(带有两个变量)来度量;对于输入为单个数字的算法,问题大小可以通过数字本身或表示二进制形式的数字所需的位数来测量,具体取决于上下文。
因此,“问题大小”的含义特定于算法解决的问题。如果您想要一个适用于所有问题的更通用的定义,则问题大小可以定义为表示输入所需的位数;例如,但是此定义不切实际,仅在理论上用于讨论问题类别(例如在多项式时间内可解决的问题)。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句