替代大O符号？

Question

下午好一切，

我们说一个hashtable有O（前提是我们有钥匙）（1）查找，而linked list有O（1）下一个节点查找（前提是我们有一个参考到当前节点）。

然而，由于如何Big-O notation作品，这不是在表达（或分化）的算法X的成本是非常有用的，VS的算法X +米的成本。

例如，即使我们的标签的哈希表的查找和链表的查找为O（1）这两个，这两个O（1）■归结到一个非常不同数量的确实步骤，

的链接列表的查找固定为x步骤数。但是，哈希表的查找是变量。哈希表的查找的成本取决于散列函数的成本，所以为哈希表的查找所需的步骤数是：X +米，

1. 其中X是固定数目

2. 和米是未知可变值

换句话说，即使我们所说的两种操作O（1），哈希表的查找成本是幅度比链表的查找的成本较高。

的大O符号是具体地约输入数据集合的大小。这确实有它的优点，但它也有它的缺点，如我们将所有非变量归并为1时我们可以看到的。我们不能再看到它里面的m变量（哈希函数）。

除了大O符号，有另一个（建立）的符号，我们可以使用用于表达固定成本O（1），这意味着X操作和可变成本O（1），这意味着x + m（m，散列函数）的操作次数？

Answer 1

问题是“操作次数”与上下文高度相关。事实上，这就是为什么大-O符号被发明出来的原因 - 它在模拟大量计算机方面似乎工作得很好。除此之外，程序员“操作”的数量并不意味着它实际需要多少时间（例如，它是否已经在缓存中？）或者硬件实际需要多少步骤（你的处理器做了什么？ - 它是否有微操作？），甚至有多少操作被指定给处理器（你的编译器为你做了什么？）。即使你试图定义一个抽象的精确概念以便有用，这些都是关注点。

所以。现在，它是Big-O与“运营” - 无论“运营”在当时对您和您的同事意味着什么。

Answer 2

字面O（1），这意味着正好1操作

除了它没有。大的O-Notation涉及与输入相关的复杂性的相对比较。如果算法确实需要一个固定的步骤数量，完全独立于输入的大小，那么确切的步骤数量并不重要。

看一看O（n）的（正规）的定义：

这意味着：有一定的k使得对于每个n功能f比函数g较小。

在上述情况下，散列表查找和链接列表查找将是f，而g将是g(n) = 1。对于每种情况，您都可以找到f(n) <= g(n) * k的k。

现在，这个k不需要固定，它可以根据平台，实现，具体硬件而有所不同。唯一有趣的一点是它存在。这就是为什么哈希表查找和链表节点查找都是O（1）：无论输入如何，它们都具有恒定的复杂度。当评估算法时，这是有趣的，而不是物理步骤。

具体地关于哈希表查找

是，散列函数确实需要的操作（根据实现）的可变量。但是，根据输入的大小，它不需要进行可变数量的操作。 Big O-Nation具体约为输入数据集合大小。散列函数需要单个元素。对于算法的评估，如果操作次数没有随着输入大小而增加，则某个函数需要10,20,50或100次操作并不重要，它是O（1）。没有办法在大的O-Notation中区分这一点，因为这不是什么大的O-Notation。

Answer 3

“〜”包含常数因子 - 见the family of bachmann functions