"O(1)访问时间"是什么意思？

我已经看到这个术语"O(1)访问时间"曾经意味着"快速",但我不明白这意味着什么.我在同一个上下文中看到的另一个术语是"O(n)访问时间".有人可以用简单的方式解释这些术语的含义吗？

也可以看看

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

8岁儿童的大O？

Karl.. 148

您将要阅读有关复杂性的顺序.

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

简而言之,O(1)意味着它需要一个恒定的时间,如14纳秒,或三分钟,无论集合中的数据量.

O(n)意味着它需要与集合大小成线性的时间量,因此设置两倍的集合将花费两倍的时间.您可能不希望将一百万个对象放入其中一个.

1> Karl..：

---

您将要阅读有关复杂性的顺序.

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

简而言之,O(1)意味着它需要一个恒定的时间,如14纳秒,或三分钟,无论集合中的数据量.

O(n)意味着它需要与集合大小成线性的时间量,因此设置两倍的集合将花费两倍的时间.您可能不希望将一百万个对象放入其中一个.

---

要迂腐,这并不意味着运行时(或操作数等)是不变的.这意味着存在一个常量,使得运行时(或操作数等)被常量限制在上面.运行时可能仍有很大的差异:例如,`int main(){int n; cin >> n; if(n == 0){sleep(60*60*24*365); } cout << n; }`是`O(1)`.

2> SingleNegati..：

---

从本质上讲,这意味着无论您的集合中有少量项目还是非常多(在硬件的限制范围内),在集合中查找值都需要相同的时间

O(n)意味着查找项目所花费的时间与集合中的项目数量成正比.

这些的典型示例是可以直接访问的数组,无论其大小如何,以及链接列表,必须从头开始按顺序遍历访问给定项目.

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

3> jason..：

---

当前回答此问题的每个答案都告诉您,这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;
}

这是因为我们必须遍历数组,一次检查一个元素.

4> Rob Walker..：

---

O(1)表示访问某些内容的时间与集合中的项目数无关.

O(N)意味着访问项目的时间与集合中项目的数量(N)成比例.

5> Bill the Liz..：

---

O(1)并不一定意味着"快速".这意味着它所花费的时间是恒定的,而不是基于函数输入的大小.常数可以快或慢.O(n)表示函数所用的时间将与函数输入的大小成正比变化,用n表示.同样,它可能快或慢,但随着n的大小增加它会变慢.

6> alexn..：

---

它被称为Big O表示法,描述了各种算法的搜索时间.

O(1)表示最坏情况下的运行时间是恒定的.对于大多数情况,这意味着你不需要实际搜索集合,你可以立即找到你正在搜索的内容.

---

@Seb:我认为这只是他的一个误称,特别是因为OP询问了访问时间.