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

Question

19 浏览2023年5月25日

匿名的 2023年4月30日

0 Comments

这个问题已有答案: 什么是“大O符号”（Big O notation）的简单解释？

我见过这个术语“O(1)访问时间”被用来表示“快速”，但我不理解它的意思。在同样的上下文中，我看到的另一个术语是“O(n)访问时间”。请有人用简单的方式解释一下这些术语的含义吗？

另请参阅

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

8岁孩子的大O符号？

admin 更改状态以发布 2023年5月25日

0

匿名的 · Answer 1 · 2023-04-30T20:57:58+00:00

本质上，这意味着在你的集合中查找一个值需要的时间无论你的集合中有少量还是非常多（在硬件的限制范围内）都是相同的。

O(n) 表示查找一项所需的时间与集合中的项数成比例。

这些的典型例子是数组，它们可以直接访问，而不受其大小影响，以及链表，必须从开始遍历以访问给定项。

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

匿名的 · Answer 2 · 2023-04-30T20:57:58+00:00

您需要详细了解复杂度排序。

简而言之，O（1）表示它需要固定的时间，例如14纳秒或三分钟，不管数据集的大小。

O(n)表示它需要与集大小成正比的时间，因此，大小为两倍的集将需要两倍的时间。您可能不想将一百万个对象放入其中之一。