152

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

也可以看看

4

16 回答 16

195

您将需要阅读复杂性顺序。

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

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

O(n) 意味着它所花费的时间与集合的大小成线性关系，因此两倍大小的集合将花费两倍的时间。您可能不想将一百万个对象放入其中之一。

于 2009-03-30T16:25:42.880 回答
42

从本质上讲，这意味着无论您的收藏中的项目数量很少还是非常多（在您的硬件限制内），在您的收藏中查找一个值都需要相同的时间

O(n) 意味着查找一个项目所需的时间与集合中的项目数成正比。

典型的例子是数组，无论它们的大小如何，都可以直接访问；链表，必须从头开始按顺序遍历才能访问给定的项目。

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

于 2009-03-30T16:25:09.107 回答
28

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

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

于 2009-03-30T16:25:18.623 回答
24

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

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

于 2010-01-08T19:19:34.483 回答
17

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

于 2009-03-30T16:41:06.557 回答
14

Here is a simple analogy; Imagine you are downloading movies online, with O(1), if it takes 5 minutes to download one movie, it will still take the same time to download 20 movies. So it doesn't matter how many movies you are downloading, they will take the same time(5 minutes) whether it's one or 20 movies. A normal example of this analogy is when you go to a movie library, whether you are taking one movie or 5, you will simply just pick them at once. Hence spending the same time.

However, with O(n), if it takes 5 minutes to download one movie, it will take about 50 minutes to download 10 movies. So time is not constant or is somehow proportional to the number of movies you are downloading.

于 2019-03-11T09:26:51.563 回答
9

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

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

于 2009-03-30T16:25:35.877 回答
7

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

于 2009-03-30T16:26:17.857 回答
6

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

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

于 2016-08-29T18:51:22.953 回答
4

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

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

于 2009-03-30T16:27:34.607 回答
3

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

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

对于列表，无论您是否知道索引，您总是需要遍历它。

于 2009-03-30T16:36:56.427 回答
2

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

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

于 2009-03-30T16:25:18.217 回答
1

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

O 也称为大 O。

于 2009-03-30T16:25:23.910 回答
1

Cormen、Leiserson、Rivest 和 Stein 的《算法导论：第二版》在第 44 页上说

由于任何常数都是 0 次多项式，我们可以将任何常数函数表示为 Theta(n^0) 或 Theta(1)。然而，后一种表示法是一种轻微的滥用，因为不清楚哪个变量趋于无穷大。我们将经常使用符号 Theta(1) 来表示常数或关于某个变量的常数函数。...我们用 O(g(n))... 表示函数集 f(n) 使得存在正常数 c 和 n0 使得 0 <= f(n) <= c*g(n)对于所有 n >= n0。...请注意，f(n) = Theta(g(n)) 意味着 f(n) = O(g(n))，因为 Theta 表示法比 O 表示法强。

如果算法在 O(1) 时间内运行，则意味着渐近不依赖于任何变量，这意味着存在至少一个正常数，当乘以 1 时大于函数的渐近复杂度（~runtime）对于超过一定数量的 n 值。从技术上讲，这是 O(n^0) 时间。

于 2009-03-30T17:08:51.467 回答
-2

O(1) 表示随机访问。在任何随机存取存储器中，访问任何位置的任何元素所花费的时间都是相同的。这里时间可以是任何整数，但唯一要记住的是在第 (n-1) 个或第 n 个位置检索元素所花费的时间将是相同的（即常数）。

而 O(n) 取决于 n 的大小。

于 2010-01-08T18:56:50.397 回答
-4

在我看来，

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

于 2012-07-27T08:21:43.687 回答