首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >可以将算法的效率建模为输入大小和时间之间的函数吗?

可以将算法的效率建模为输入大小和时间之间的函数吗?
EN

Stack Overflow用户
提问于 2020-05-13 16:58:36
回答 1查看 29关注 0票数 0

考虑以下算法(仅作为示例,因为实现效率明显较低):

代码语言:javascript
复制
def add(n):
    for i in range(n):
        n += 1
return n

该程序将一个数字与自身相加,然后返回它。现在,算法的效率被sometimes建模为输入大小和算法必须计算的原始步数之间的函数。在这种情况下,输入是一个整数n,并且随着n的增加,完成算法所需的步骤数也会增加(在这种情况下是线性的)。但是,输入的大小真的增加了吗?让我们假设运行程序的机器表示的是8位整数。因此,如果我将假设输入3增加到7,所涉及的位数保持不变: 00000011 -> 00000111。然而,计算算法所需的步骤增加了。因此,似乎算法效率并不总是正确的,可以将算法效率建模为输入大小和计算步骤之间的关系。有人能解释一下我哪里错了吗?或者如果我没有错,为什么将算法的效率建模为输入大小和要计算的原始步数之间的函数仍然有意义?

EN

回答 1

Stack Overflow用户

发布于 2020-05-13 17:11:50

S为输入n的大小。(通常我们会对这种大小使用n,但由于该参数也称为n,这会让人感到困惑)。对于正nSn之间存在关系,即S = ceil(ln(n))。该程序循环n次,并且由于n < 2^S,它在大多数2^S时间循环。您还可以显示它至少循环了1/2 * 2^S次,因此运行时(以循环迭代次数衡量)是Theta(2^S)

这表明有一种方法可以将运行时建模为大小的函数,即使它不是精确的。

它是否有意义。在您的示例中,它不是很多,但是如果您的输入是一个用于排序的数组,那么将size作为数组中元素的数量是有意义的。(例如,它通常用于对不同排序算法完成的比较次数进行建模)。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/61770346

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档