java - 链表 getValue(int n) 应该是 O(n/2)

Question

标准链表实现是双向链接的。因此我们分别有一个 headNode 和一个 tailNode 。我已阅读 getValue(int n)，因为返回列表中第 n 个元素处保存的数据部分。现在假设我们从 headNode 开始对链表进行顺序搜索，如果该位置是列表中的最后一个元素，最坏的情况将是 O(n)。然而，如果我们检查 n > size/2 ，那么我们就知道是否从 headNode 或 tailNode 开始遍历。这意味着它将执行 O(n/2)，可以重写为 O(1/2n)。

根据 Big O Notation 的规则，系数并不重要，因此最坏的情况仍然是 O(n)。我发现这个逻辑有一个缺陷，因为如果我们有一个包含大量节点的列表，比如 100 万个，那么 500, 000 的最坏情况比 1, 000, 000 的最坏情况要好得多。最坏的情况是如果我们要搜索的位置实际上是 size/2 。我实现了这段代码，发现当传递的位置小于 size/2 时，它们以相同的速度执行，但是，当传递的位置大于 size/时2、它的执行速度明显更快。我的问题是，当这样一个简单的解决方案将最坏的情况减少一半时，我们怎么能说这是 O(n) 呢？显然系数很重要，我不明白我们如何得出它们无关的结论。这是代码:

//This is headed by firstNode and tailed by lastNode
public Node getValue(int position)
{
    if (!isEmpty() && position <= size)
    {

        if (position > (size / 2))
            return traverseReverse(position);
        else
            return sequentialSearch(position);

    }

    return null;
}

private Node traverseReverse(int searchIndex)
{
    Node currentNode = lastNode;
    int position = size;
    while (currentNode != null)
    {
        if (position == searchIndex)
            return currentNode;

        position--;
        currentNode = currentNode.previous;
    }

    return null;
}

private Node sequentialSearch(int position)
{
    Node currentNode = firstNode;
    int n = 0;

    while (currentNode != null)
    {
        if (n == position)
            return currentNode;

        n++;
        currentNode = currentNode.next;
    }

    return null;
}

Answer 1

复杂度和运行时间是相关的概念，但并不完全相同。随着 n 的增加，复杂性显示了 n 与运行时之间的关系。

无论系数如何，线性关系都是 O(n)。如果您想比较最坏情况的运行时间，请务必这样做，但复杂性分析不是正确的工具。这只是一个起点。

无论您从前面还是后面搜索链接列表，您需要查看的平均项目数与其大小成正比。