Sedgewick算法4,为什么BinarySearchST将FrequencyCounters的测试成本低于SequentialSearchST？

Question

我正在阅读算法第4版.我在阅读第3章搜索时遇到了一些问题.从成本汇总中,BinarySearchST的插入成本(在最坏的情况下为2N)比SequentialSearchST(在最坏的情况下为N)稍差.但使用VisualAccumulator(绘制图表)的FrequencyCounter测试显示

对于长度为8或更长的字,返回FrequencyCounter的put()操作的成本,我们看到,对于SequentialSearchST,每次操作的平均成本从2,246比较(加上数组访问)减少到BinarySearchST的484.

BinarySearchST的put()操作是否需要比SequentialSearchST更多的比较(加上数组访问)？

另一个问题,对于BinarySearchST,这本书说

命题B(续).在最坏的情况下,将一个新密钥插入一个大小为N的有序数组中使用~2N数组访问,因此在最坏的情况下将N个密钥插入一个最初为空的表使用~N ^2个数组访问

当我查看BinarySearchST的代码时,我认为将一个新密钥插入一个大小为N的有序数组中会使用~4N数组访问.

    public void put(Key key, Value val)  {
    if (key == null) throw new IllegalArgumentException("first argument to put() is null"); 

    if (val == null) {
        delete(key);
        return;
    }

    int i = rank(key);

    // key is already in table
    if (i < n && keys[i].compareTo(key) == 0) {
        vals[i] = val;
        return;
    }

    // insert new key-value pair
    if (n == keys.length) resize(2*keys.length);

    for (int j = n; j > i; j--)  {
        keys[j] = keys[j-1];
        vals[j] = vals[j-1];
    }
    keys[i] = key;
    vals[i] = val;
    n++;

    assert check();
} 

因为对于循环中的每个i,有4个数组访问,2个用于键读取和更新,2个用于值读取和更新.那么为什么道具B说它使用~2N阵列访问？

Answer 1

put()“的操作不应该BinarySearchST比 需要更多的比较（加上数组访问）吗SequentialSearchST？”

不，因为这本书之前讨论的是最糟糕的情况。

最坏情况和平均情况是不同的。从书中的下一句话我们可以读到：“和以前一样，这个成本甚至比分析预测的还要好，而且额外的改进很可能再次由应用程序的属性来解释……”

“那么为什么道具 B 说它使用~2N数组访问呢？”

在某些时候，我认为，你是对的，形式上有 4N 次访问，但是

如果我们将循环重写为：

keys[j] = keys[j-1];
keys[j-1] = keys[j-2];
keys[j-2] = keys[j-3];
...
keys[i+1] = keys[i];

这是否意味着我们仍然使用4N访问？我认为 JIT 编译器可以以正确的方式优化循环。

我们还可以假设数组通常表示为线性内存，计算机将数据读取到虚拟页面中，因此，这样的页面已经被访问并且位于缓存中。