“O（1）访问时间”是什么意思？

2018-06-13 22:10:01

我曾经看过这个术语“O（1）访问时间”，意思是“很快”，但我不明白它的含义。我在同一个环境中看到的另一个术语是“O（n）访问时间”。有人可以用简单的方式解释这些术语的含义吗？

也可以看看

大O符号是什么？你用它吗？

八岁大的孩子？

您将要阅读复杂性顺序。

http://en.wikipedia.org/wiki/Big_O_notation

简而言之，O（1）意味着无论集合中的数据量如何，它都需要一个固定的时间，如14纳秒或3分钟。

O（n）意味着它需要的时间量与集合的大小成线性关系，所以设置两倍的大小将需要两倍的时间。您可能不希望将一百万个对象放入其中。

实质上，这意味着无论您的集合中是否有少量的项目或非常多的项目（在硬件的限制范围内），都需要花费相同的时间来查找集合中的值，

O（n）意味着查找项目所需的时间与集合中项目的数量成正比。

这些典型的例子是数组，它们可以直接访问，不管它们的大小和链接列表，它们必须从头开始访问给定的项目。

通常讨论的其他操作是插入。集合可以是O（1）用于访问，但O（n）用于插入。实际上，一个数组具有这种行为，因为要在中间插入一个项目，您必须将每个项目复制到下一个插槽中才能将其移到右侧。

当前对这个问题做出回应的每一个答案都告诉你O(1)意味着恒定的时间（不管它发生在什么时候;可以是运行时间，操作次数等等）。这是不准确的。

要说运行时间为O(1)意味着存在一个常量c ，以便运行时受c ，而与输入无关。例如，返回n整数数组的第一个元素是O(1) ：

int firstElement(int *a, int n) {
    return a[0];
}

但是这个函数也是O(1) ：

int identity(int i) {
    if(i == 0) {
        sleep(60 * 60 * 24 * 365);
    }
    return i;
}

这里的运行时间限制在1年以上，但大部分时间运行时间为纳秒级。

要说运行时间是O(n)意味着存在一个常量c ，以便运行时受c * n ，其中n测量输入的大小。例如，通过以下算法找出n整数的未排序数组中出现的特定整数的个数为O(n) ：

int count(int *a, int n, int item) {
    int c = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] == item) c++;
    }
    return c;
}

这是因为我们必须遍历整个数组来检查每个元素。

链接地址: http://www.djcxy.com/p/39663.html