"恒定时间"意味着什么？

Question

我是一名程序员,但没有计算机科学背景,所以最近我一直在关注优秀的MIT OpenCourseWare计算机科学和编程入门.在此过程中,问题是:"任何程序是否只使用函数定义和调用,基本算术运算符,赋值和条件在恒定时间内运行？"

我认为答案是肯定的,因为所有这些操作看起来都很简单.但正如你聪明的人可能已经知道的那样,正确的答案是否定的,显然是因为无限期递归的可能性.

似乎我只是不理解"在恒定时间内"的含义.我想象的意思是,这听起来只是意味着一个简单的操作需要花费已知的时间来完成.我接受递归可以导致你的程序永远运行,但不是每个操作仍然需要有限和可测量的时间每个...即使现在有无限数量的它们？或者答案是否意味着无法有效地说两个无限递归程序需要花费相同的时间来运行？

如果有人能给我一个"在恒定时间内"的权威定义及其含义,我将非常感激!

Answer 1

恒定时间实际上意味着您可以给程序运行多长时间的上限,这不受任何输入参数的影响.

比较线性时间(对于某些输入n- 通常实际上是输入数据的大小而不是直接值) - 这意味着所用时间的上限可以表示mn + k为某些值的m和k.

请注意,这并不意味着程序将花费相同的时间用于任何输入数据,因为它在恒定时间内运行.例如,考虑这种方法:

int foo(int n)
{
    if (n == 0)
    {
        return 0;
    }
    int j = n + 1;
    int k = j * 2;
    return k;
}

在n非零的情况下,这比在零的情况下做更多的工作.然而,它仍然是恒定的时间 - 最多,它将进行一次比较,一次加法和一次乘法.

现在将它与递归函数进行比较:

public int foo(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    return n * foo(n - 1);
}

这将减少n时间 - 因此它是线性的n.但是,你可能比线性更糟糕.考虑这种计算Fibonacci数的方法:

public int fib(int n)
{
    if (n == 0)
    {
        return 0;
    }
    if (n == 1)
    {
        return 1;
    }
    return fib(n - 2) + fib(n - 1);
}

这看起来并不比以前的版本差得多 - 但现在这是指数级的(上限最容易表示为O(2 ⁿ).它仍然只使用简单的比较,加法和函数调用.

Answer 2

"恒定时间"意味着操作将在一定时间内(或存储空间 - 这是经常测量的另一个事件)执行,与输入大小无关.通常你选择一个变量(让我们使用n)来表示输入大小.

O(1) - 恒定时间 - 运行时间不依赖于 n

O(n)-线性时间-运行时间是线性比例,以n

O(n^2)- 二次时间 - 运行时间与平方成正比 n

这只是几个例子; 可能性是无止境.请参阅有关复杂性的Wiki文章

以下是一些特定的方法,只由您提到的操作组成的程序可能需要不同的时间:

int n = // some value
doSomething
doSomething
doSomething

注意它是如何长度的三个东西,独立于什么n. O(1)

int n = // some value
def f(n):
    if n == 0 return
    doSomething
    f(n-1)
f(n)

现在我们为每个值0..n(线性时间)运行一些东西O(n)

我们可以有一点乐趣 -

int n = //some value
def f(n):
    if n == 0 return
    doSomething
    f(n-1)
    f(n-1)

这里的运行时间是多少？(即我们执行了多少事？):)

Answer 3

"恒定时间"具有相同的含义"O(1)",这并不意味着一个算法在固定的时间量运行时,它只是意味着它是不成比例的长度/尺寸/大小输入.即,对于任何输入,它可以在相同的时间内计算(即使该时间量真的很长).