小编Gra*_*tly的帖子

我正在阅读算法第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 > …

考虑派生类的基类,其中基类应该为其所有派生提供一些(多态)方法,例如armithmetic或bitweise重载运算符.派生类不应修改此操作以确保正确执行.但是,与此同时,我想进行评估 - 在我的示例中函数isError() - 运算符必须是子类和纯虚拟的,因此必须定义:

class Mom
{
public:
    virtual bool operator && (const Mom&) const final
    {
        return this->isError() && p_rOther.isError();
    }
private:
    virtual bool isError() = 0;
};

鉴于当前标准,似乎不允许这样做,因为"纯虚拟性"意味着子类必须实现基类的所有虚函数,而"final"关键字与此范例相矛盾.

任何建议或想法如何处理这个矛盾？