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 表示法涉及与输入相关的复杂性的相对比较。如果算法确实采用恒定数量的步骤，完全独立于输入的大小，那么确切的步骤数量并不重要。

看一下 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)。在大 O 表示法中无法区分这一点，因为这不是大 O 表示法的目的。