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

从本质上讲，它意味着无论您的集合中有少量项目还是非常非常多(在硬件的约束范围内) ，在集合中查找值所需的时间是相同的

O (n)表示查找一个条目所花费的时间与集合中条目的数量成正比。

典型的例子是数组和链表，无论数组大小如何，都可以直接访问; 链表必须从一开始就进行遍历，才能访问给定的项目。

通常讨论的另一种操作是插入。集合可以是 O (1)表示访问，但是可以是 O (n)表示插入。事实上，数组就具有这种行为，因为要在中间插入一个项目，您必须将每个项目向右移动，将其复制到下面的槽中。

这意味着访问时间是恒定的。无论您访问的是100条还是100,000条记录，检索时间都是相同的。

相反，O (n)访问时间表示检索时间与访问的记录数量成正比。

O (1)表示访问某物的时间与集合中的项目数无关。

O (N)表示访问项的时间与集合中项的数量(N)成正比。

这意味着访问需要固定的时间，即不依赖于数据集的大小。O (n)表示访问将线性地依赖于数据集的大小。

O 也被称为大 O。

它被称为 大 O 符号，描述了各种算法的搜索时间。

O (1)表示最坏情况下的运行时间是常数。在大多数情况下，这意味着您实际上不需要搜索集合，您可以立即找到您正在搜索的内容。

你会想要读一读复杂度的顺序。

Http://en.wikipedia.org/wiki/big_o_notation

简而言之，O (1)意味着它需要一个固定的时间，比如14纳秒，或者3分钟，与集合中的数据量无关。

O (n)意味着它需要一定的时间与集合的大小成线性关系，所以一个集合的大小的两倍将需要两倍的时间。你可能不想把一百万个对象放进其中一个里面。

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

基本上，o (1)意味着它的计算时间是常数，而 o (n)意味着它将依赖于 线性的的输入大小-即循环通过一个数组有 o (n)-只是循环-因为它取决于项的数量，而计算两个普通数字之间的最大值有 o (1)。

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

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

对于 array，如果具有正确的索引值，则可以立即访问数据。 (如果您不知道索引并且必须遍历数组，那么它将不再是 O (1))

对于 list，无论您是否知道索引，始终需要循环访问它。

O (1)不一定意味着“迅速”。这意味着它所花费的时间是常数，没有基于函数输入的大小。常量可快可慢。O (n)表示函数所花费的时间将与函数的输入大小成正比，用 n 表示。同样，它可以快也可以慢，但是随着 n 的增加它会变慢。

《算法导论: 第二版》(Leiserson)第44页说

因为任何常数都是0度 多项式，我们可以表示任意 作为 Θ (n ^ 0)的常数函数，或者 Θ (1)后一个符号是 a 然而，这只是小小的虐待，因为它确实是 不清楚变量趋向于什么 我们应该经常使用 表示 Θ (1)表示 a 具有常数或常数的函数 考虑到一些变量... 我们 用 O (g (n))表示... 的集合 函数 f (n)使得存在 正常数 c 和 n0使得 0 < = f (n) < = c * g (n)对于所有 n > = n0。 注意 f (n) = Θ (g (n)) 暗示 f (n) = O (g (n)) ，因为 Θ 符号比 O 符号强。

如果一个算法在 O (1)时间内运行，这意味着渐近不依赖于任何变量，这意味着至少存在一个正常数，这个正常数乘以一比函数的渐近复杂度(~ 运行时间)要大。技术上来说，是 O (n ^ 0)时间。

O (1)表示随机存取。在任何随机存取记忆体中，存取任何位置的任何元素所需的时间是相同的。这里的时间可以是任何整数，但是需要记住的是在(n-1) th 或 nth 位置检索元素所花费的时间将是相同的(即常量)。

而 O (n)取决于 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;
}

这是因为我们必须迭代遍历数组，每次检查一个元素。

在我看来,

O (1)表示一次执行一个操作或指令的时间是一个，在时间复杂度分析算法的最佳情况下。

无论数据集 n 如何，O(1)始终在同一时间执行。 O (1)的一个例子是使用 index 访问其元素的 ArrayList。

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

这里有一个简单的类比; 假设你正在下载电影在线，与 O (1) ，如果它需要5分钟下载一部电影，它仍然需要同样的时间下载20部电影。所以不管你下载了多少部电影，不管是一部还是20部，它们都需要相同的时间(5分钟)。这种类比的一个常见例子是，当你去电影图书馆时，无论你选择一部电影还是5部，你都会一次性选择它们。所以花了同样的时间。

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