考虑以下算法(仅作为示例,因为实现效率明显较低):
def add(n):
for i in range(n):
n += 1
return n该程序将一个数字与自身相加,然后返回它。现在,算法的效率被sometimes建模为输入大小和算法必须计算的原始步数之间的函数。在这种情况下,输入是一个整数n,并且随着n的增加,完成算法所需的步骤数也会增加(在这种情况下是线性的)。但是,输入的大小真的增加了吗?让我们假设运行程序的机器表示的是8位整数。因此,如果我将假设输入3增加到7,所涉及的位数保持不变: 00000011 -> 00000111。然而,计算算法所需的步骤增加了。因此,似乎算法效率并不总是正确的,可以将算法效率建模为输入大小和计算步骤之间的关系。有人能解释一下我哪里错了吗?或者如果我没有错,为什么将算法的效率建模为输入大小和要计算的原始步数之间的函数仍然有意义?
发布于 2020-05-13 17:11:50
让S为输入n的大小。(通常我们会对这种大小使用n,但由于该参数也称为n,这会让人感到困惑)。对于正n,S和n之间存在关系,即S = ceil(ln(n))。该程序循环n次,并且由于n < 2^S,它在大多数2^S时间循环。您还可以显示它至少循环了1/2 * 2^S次,因此运行时(以循环迭代次数衡量)是Theta(2^S)。
这表明有一种方法可以将运行时建模为大小的函数,即使它不是精确的。
它是否有意义。在您的示例中,它不是很多,但是如果您的输入是一个用于排序的数组,那么将size作为数组中元素的数量是有意义的。(例如,它通常用于对不同排序算法完成的比较次数进行建模)。
https://stackoverflow.com/questions/61770346
复制相似问题