language-agnostic - Big-O 符号的替代品？

Question

大家下午好

我们说 hashtable有 O(1) 查找(假设我们有 key )，而 linked list查找下一个节点的时间复杂度为 O(1)(前提是我们有对当前节点的引用)。

然而，由于Big-O notation有效，它在表达(或区分)算法 x 的成本与算法 x + m 的成本方面不是很有用。

例如，即使我们将哈希表的查找和链表的查找标记为 O(1)，这两个 O(1) 归结为非常不同的步骤数，

链表的查找固定在 x 步数。但是，哈希表的查找是可变的。哈希表的查找成本取决于哈希函数的成本，因此哈希表查找所需的步骤数为:x + m,

1. 其中x是一个固定数

2. 和m是一个未知的变量值

换句话说，即使我们将这两个操作都称为 O(1)，哈希表查找的成本比链表查找的成本高数量级。

Big-O 表示法专门针对输入数据集合的大小。这确实有它的优点，但也有它的缺点，正如我们将所有非 n 变量折叠并归一化为 1 时所看到的那样。我们看不到里面的 m 变量(哈希函数)它了。

除了 Big-O 表示法之外，是否有另一种(已建立的)表示法我们可以用来表达固定成本 O(1)，这意味着 x 操作和可变成本 O(1) 这意味着 x + m(m，哈希函数)操作次数？

Answer 1

literal O(1) which means exactly 1 operation

但事实并非如此。大 O-Notation 涉及与输入相关的复杂性的相对比较。如果算法确实采用恒定数量的步数，完全独立于输入的大小，那么确切的步数并不重要。

看看 O(n) 的(非正式)定义:

意思是:有某个k这样对于每个 n函数f小于函数 g .

在上面的例子中，哈希表查找和链接列表查找将是 f , 和 g将是 g(n) = 1 .对于每种情况，您都可以找到 k那f(n) <= g(n) * k .

现在，这个 k不需要固定，它可能因平台、实现、特定硬件而异。唯一有趣的一点是它存在。这就是哈希表查找和链表节点查找都是 O(1) 的原因:无论输入如何，两者都具有恒定的复杂性。在评估算法时，这才是有趣的，而不是物理步骤。

特别是关于哈希表查找

是的，哈希函数确实需要可变数量的操作(取决于实现)。但是，它不会根据输入的大小进行可变数量的操作。 Big O-Nation 特别是关于输入数据集合的大小。哈希函数采用单个元素。对于算法的评估，某个函数是否需要 10、20、50 或 100 次操作并不重要，如果操作数不随着输入大小的增加而增加，则为 O(1)。在 big O-Notation 中无法区分这一点，因为这不是 big O-Notation 的目的。