algorithm - 对于 O(1) 中的一系列数字，如何创建一个返回相同值的函数？

Question

例如

H: [0, 20] -> "a"
H: [21: 25] -> "y"
H: [26: 132] -> "z"

无论我输入多少范围，如何制作 H 以便函数花费恒定时间（以及插入恒定时间）？这甚至可能吗？

Answer 1

您可以为此使用一个简单的数组：

[0] -> "a"
[1] -> "a"
[2] -> "a"
[3] -> "a"
[4] -> "a"
[5] -> "a"
...
[20] -> "a"
[21] -> "y"
[22] -> "y"
[23] -> "y"
[24] -> "y"
[25] -> "y"
[26] -> "z"
...
[132] -> "z"

这为您提供 O(1) 查找。您可以对键是索引的哈希表执行相同的操作，但性能会差得多。这种方法有多种变体（例如使用哈希表或一些延迟加载的构造），但它们都处理一对一的映射。

如果由于内存限制而无法进行一对一映射，则无法使用 O(1) 执行此操作，因为您将始终必须遍历已注册的范围，因此充其量可以是 O(log (n)) 其中 n 是范围数。

Answer 2

是的，只需使用查找表。使用您希望由该范围表示的值初始化每个范围的表，然后返回索引处的值。像这样的东西：

const char *lookup(int index)
{
    static const char *table[] = {
        "foo",
        "foo",
        "foo",
        "foo",
        "bar",
        "bar",
        "quirk",
        "quirk",
        "quirk"
    };
    return table[index];
}

这将返回"foo"range [0, 3]、"bar"range[4, 5]和"quirk"range [6, 8]。