“在恒定时间内”是什么意思？意味着？

Question

我是一名程序员，但没有计算机科学背景，所以最近我一直在关注优秀的麻省理工学院开放课程，介绍计算机科学和编程。在此过程中，有人提出这样的问题：“仅使用函数定义和调用、基本算术运算符、赋值和条件编写的程序是否会在恒定时间内运行？”

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

看来我只是不明白“在恒定时间内”的含义。按照我想象的方式，听起来这只是意味着一个简单的操作需要已知的时间才能完成。我承认递归可以导致你的程序永远运行，但是每个单独的操作是否仍然花费有限且可测量的时间......即使现在有无限数量的操作？或者答案是否仅仅意味着两个无限递归程序不能有效地说花费相同的时间来运行？

如果有人能给我“恒定时间”的权威定义及其含义，我将非常感激！

Answer 1

恒定时间实际上意味着您可以为程序运行所需的时间指定一个恒定上限，该上限不受任何输入参数的影响。

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

请注意，这并不意味着程序将花费相同的时间来处理任何输入数据，仅仅因为它以恒定的时间运行。例如，考虑以下方法：

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

在 n 不为零的情况下，它比在 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);
}

这看起来并不比以前的版本差多少 - 但现在这是指数（上限最容易用术语来表达）不过，它仍然只使用简单的比较、加法和函数调用。

Answer 2

“恒定时间”意味着操作将在一定的时间（或内存空间 - 这是经常测量的另一件事）内执行，独立于输入大小。通常您会选择一个变量（让我们使用n）来指示输入大小。

O(1) - 常数时间 - 运行时间不依赖于 n

O(n) - 线性时间 - 运行时间为 与 n 线性比例

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

这些只是几个例子；可能性是无限的。请参阅关于复杂性的维基文章，

这里有一些具体的方法，仅由您提到的操作组成的程序可能会采取不同数量的操作。 time：

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)”具有相同的含义，这并不意味着算法在固定的时间内运行，而只是意味着它不与输入的长度/大小/大小。即，对于任何输入，都可以在相同的时间内计算出来（即使该时间确实很长）。

Answer 4

“恒定时间”通常意味着计算结果所需的时间与输入的大小无关。

例如。在大多数托管语言中，无论列表有多大，计算列表/向量的长度都是在恒定时间内完成的。大小存储为单独的字段，并随着列表的增长和缩小而更新。但计算计数就像读取字段一样简单。

计算双向链表的大小通常不是常数时间。该列表通常可以在两端发生变化，因此没有中央位置来存储计数。因此，确定列表的长度需要访问它并确定其中有多少元素。因此，随着列表的增长，计算答案所需的时间也会增加。

Answer 5

“在恒定时间内”意味着无论输入是什么，程序的运行时间都不会超过已知的时间量。

将阶乘函数视为反例。比如说 5 的阶乘计算如下：

5! = 5 * 4 * 3 * 2 * 1 = 120

这显然比计算 10 的阶乘花费的时间更少，因为要执行后者，程序必须再执行五次乘法：

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

因此，“恒定时间”并不意味着我们知道程序在每种情况下将运行多长时间，但它的运行时间永远不会超过已知的时间量（上限）。

Answer 6

这里的恒定时间意味着不依赖于输入数量（而不是输入本身），如果不允许 for 或 goto，则使其依赖于输入数量的唯一方法是通过条件和递归。尽管您可能会认为某些有争议的解决方案不需要递归。
例如。 （在C中）

if(ReadInput()) DoSomeThing();
if(ReadInput()) DoSomeThing();
if(ReadInput()) DoSomeThing();
if(ReadInput()) DoSomeThing();

Answer 7

真正需要考虑的重要事情是时间如何随着元素数量的变化而变化。恒定时间意味着无论涉及多少元素，时间都保持不变（外行的解释）。

Answer 8

如果程序永远运行，那么它不会在已知的时间内完成，因为它没有完成。我们将“恒定时间”的概念应用于整个程序的运行，而不是每个单独的步骤。

“恒定时间”是指“时间不依赖于输入量”。