3

在准备面试时，我遇到了一些让我质疑我对大 O 常数时间算法的理解的事情。

LeetCode 上的一个问题要求创建 LFU 缓存问题的解决方案。

有3种方法可以实现：

构造函数 - 输入：int 容量

获取 - 输入：int 键 - 输出：int

设置 - 输入：int 键，int 值

容量表示您一次可以保存的缓存键/值对的最大数量。当容量被破坏时，您必须弹出访问频率最低的对。

很明显，您必须跟踪每个项目被访问的次数。

在问题的底部，它询问您是否可以在 O(1) 时间内获取和设置。

我正在研究这个的多个提议的实现，一长串的人都同意他们是恒定时间实现的例子，但对我来说，他们看起来像 O(N)。

有关完整示例，请参见此处： https ://leetcode.com/problems/lfu-cache/discuss/94515/Java-O(1)-Accept-Solution-Using-HashMap-DoubleLinkedList-and-LinkedHashSet?page=1

但是这个例子中的相关方法在下面的代码块中。注意 valueHash 和 nodeHash 都是 java 哈希表。

public int get(int key) {
    if (valueHash.containsKey(key)) {
        increaseCount(key);
        return valueHash.get(key);
    }
    return -1;
}

    public void set(int key, int value) {
    if ( cap == 0 ) return;
    if (valueHash.containsKey(key)) {
        valueHash.put(key, value);
    } else {
        if (valueHash.size() < cap) {
            valueHash.put(key, value);
        } else {
            removeOld();
            valueHash.put(key, value);
        }
        addToHead(key);
    }
    increaseCount(key);
}

方法调用 Hashtable.containsKey 和 Hashtable.get，实现线性搜索。所以最坏情况的时间复杂度是 O(N) 对吧？我错过了什么？

4

1 回答 1

4

无论您使用哪种数据结构，它都有一些悲观的搜索时间 T(n)，这取决于存储的项目数 n。如果您设置了一些最大容量 Nmax，并在程序执行期间保持恒定，如问题陈述中特别要求的那样，那么处理任何请求的最大时间为 T(Nmax)，它是恒定的。

感谢 @Zabuza 强调 Nmax 的恒定性。

于 2018-03-04T16:11:38.087 回答