“O（1）访问时间”是什么意思？
我曾经看过这个术语“O（1）访问时间”，意思是“很快”，但我不明白这是什么意思。 我在同一个环境中看到的另一个术语是“O（n）访问时间”。 难道有人能以简单的方式解释这些术语的含义吗？
也可以看看
- 大O符号是什么？ 你用它吗？
- 八岁的大O？
您将要阅读复杂顺序。
http://en.wikipedia.org/wiki/Big_O_notation
简而言之，O（1）意味着无论集合中的数据量如何，它都需要一个固定的时间，如14纳秒或3分钟。
O（n）表示所花费的时间与集合的大小成线性关系，所以设置两倍的大小将花费两倍的时间。 你可能不想把一百万个对象放到其中。
从本质上讲，这意味着在集合中查找值需要花费相同的时间，无论您的集合中是否有less量的项目，还是非常多（在硬件的限制范围内）
O（n）表示查找项目所需的时间与集合中项目的数量成正比。
这些典型的例子是数组，可以直接访问数组，无论数据的大小和链表是多less，必须从头开始访问给定的数据项。
通常讨论的其他操作是插入。 集合可以是O（1）用于访问，但O（n）用于插入。 实际上，一个数组具有这种行为，因为要在中间插入一个项目，您必须将每个项目复制到下一个插槽中。
当前对这个问题做出回答的每一个答案都告诉你， O(1)意味着恒定的时间（无论发生什么测量;可能是运行时间，操作次数等等）。 这是不准确的。
说运行时为O(1)意味着有一个常数c ，使得运行时以c为界，独立于input。 例如，返回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测量input的大小。 例如，通过下面的algorithm找出n整数的未sorting数组中出现的特定整数的个数为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）并不一定意味着“很快”。 这意味着所花费的时间是恒定的，而不是基于函数input的大小。 常量可能是快或慢。 O（n）意味着函数所花费的时间将与函数input的大小成正比，用n表示。 再次，它可能是快或慢，但随着n的大小增加，它会变慢。
O（1）表示访问某个东西的时间与集合中的项目数量无关。
O（N）表示访问项目的时间与集合中项目的数量（N）成正比。
它被称为Big O符号 ，并描述了各种algorithm的search时间。
O（1）表示最坏的运行时间是恒定的。 对于大多数情况下，这意味着你不会真的需要search集合，你可以find你正在寻找的东西。
“大O符号”是一种expressionalgorithm速度的方法。 n是algorithm处理的数据量。 O(1)表示不pipe有多less数据，它都会在一定的时间内执行。 O(n)表示它与数据量成比例。
基本上，O（1）意味着它的计算时间是恒定的，而O（n）意味着它将依赖于input的大小 – 即循环一个数组有O（n） – 循环 – 因为它取决于数的项目，而计算之间的最大值为普通数字有O（1）。
维基百科也可能有所帮助： http ： //en.wikipedia.org/wiki/Computational_complexity_theory
O(1)总是在同一时间执行而不pipe数据集n。 O（1）的一个例子是一个ArrayList访问其索引元素。
O(n)也被称为线性顺序（linear order），性能将会线性增长，并与input数据的大小成正比。 O（n）的一个例子是在随机位置的ArrayList插入和删除。 随着随机位置的每个后续插入/删除操作，都会导致ArrayList中的元素向内部数组的左右移动，以保持其线性结构，更不用说新build数组和复制元素到新的arrays，因此占用昂贵的处理时间，从而损害性能。
这意味着访问时间是不变的。 无论您是访问100或100,000条logging，检索时间将是相同的。
相反，O（n）访问时间将表明检索时间与您正在访问的logging数成正比。
这意味着访问需要一段时间，即不依赖于数据集的大小。 O（n）表示访问将线性地依赖于数据集的大小。
O也被称为big-O。
区分O（1）和O（n）最简单的方法是比较数组和列表。
对于数组，如果你有正确的索引值，你可以立即访问数据。 （如果你不知道索引并且不得不循环遍历数组，那么它将不会是O（1））
对于列表，无论您是否了解索引，都需要循环访问。
algorithm介绍：第二版由Cormen，Leiserson，Rivest＆Stein在第44页上说
由于任何常数都是一个0次多项式，所以我们可以表示为Theta（n ^ 0）或Theta（1）的任何常数函数。 后面的表示法是一个小的滥用，但是，因为不清楚哪个variables趋于无穷大。 我们经常使用符号Theta（1）来表示关于某个variables的常量或者常量函数。 我们用O（g（n））…表示函数集合f（n），使得存在正常数c和n0使得0 <= f（n）<= c * g（n）对于所有n> = n0。 …注意，f（n）=θ（g（n））意味着f（n）= O（g（n）），因为Theta符号比O符号更强。
如果algorithm在O（1）时间运行，则意味着渐近地不依赖于任何variables，这意味着至less存在一个正的常数，当乘以1时大于函数的渐近复杂度（〜运行时间）对于超过一定数量的n的值。 从技术上讲，这是O（n ^ 0）时间。
O（1）表示随机存取。 在任何随机存取存储器中，访问任何位置的任何元素所用的时间是相同的。 这里的时间可以是任何整数，但唯一要记住的是在第（n-1）或第n个位置检索元素所花费的时间将是相同的（即恒定的）。
而O（n）取决于n的大小。
根据我的观点，
O（1）表示执行一次操作或指令的时间是一次，algorithm的时间复杂度分析是最好的情况。
