computer-science - “in constant time”意味着什么？

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中是线性的。但是，您可能会比线性情况差得多。考虑以下用于计算斐波纳契数的方法:

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

这看起来并不比以前的版本差很多-但这现在是指数的(上限最容易用O(2n)表示。尽管如此，它仍然仅使用简单的比较，加法和函数调用。