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

Question

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

也可以看看

• 什么是大O符号？你用它吗？
• 8岁儿童的大O？

Answer 1

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

Answer 6

这是一个简单的类比；想象你在线下载电影，O(1)，如果下载一部电影需要 5 分钟，那么下载 20 部电影仍然需要相同的时间。因此，无论您下载多少部电影，无论是一部电影还是 20 部电影，它们都将花费相同的时间（5 分钟）。这个类比的一个正常例子是，当你去一个电影库时，无论你是拍一部电影还是五部电影，你都会一次选择它们。因此花费相同的时间。

然而，对于 O(n)，如果下载一部电影需要 5 分钟，那么下载 10 部电影大约需要 50 分钟。所以时间不是恒定的，或者与您下载的电影数量成正比。

Answer 7

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

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

Answer 8

基本上，O(1) 意味着它的计算时间是恒定的，而 O(n) 意味着它将线性依赖取决于输入的大小 - 即循环遍历数组有 O(n) - 只是循环 - 因为它取决于数字项，而计算两个普通数字之间的最大值的时间复杂度为 O(1)。

维基百科也可能有帮助：http ://en.wikipedia.org/wiki/Computational_complexity_theory

Answer 9

“Big O notation”是一种表达算法速度的方式。n是算法正在处理的数据量。O(1)意味着，无论有多少数据，它都会在恒定时间内执行。O(n)意味着它与数据量成正比。

Answer 10

O(1)无论数据集 n 为何，总是同时执行。O(1) 的一个例子是使用索引访问其元素的 ArrayList。

O(n)也称为线性顺序，性能将线性增长，并与输入数据的大小成正比。O(n) 的一个例子是在随机位置插入和删除 ArrayList。由于每个随机位置的后续插入/删除都会导致 ArrayList 中的元素向其内部数组的左向右移动以保持其线性结构，更不用说创建新数组和从旧数组复制元素了新数组占用昂贵的处理时间，从而损害性能。

Answer 11

区分 O(1) 和 O(n) 的最简单方法是比较数组和列表。

对于数组来说，如果有正确的索引值，就可以立即访问数据。（如果你不知道索引并且必须循环遍历数组，那么它就不再是 O(1) 了）

对于列表，无论你是否知道索引，你总是需要循环它。