这个哈希函数的时间复杂度是多少

Question

我有一个哈希函数，我想知道它是否是常量。 由于数组字的长度是常数，这是否意味着该函数在 Big O 表示法中是常数？

public int hash(String s) {
    if (s.length() > 7)
        return -1;
    for (int i = 0; i < word.length; ++i) {
        if (word[i].compareTo(s) == 0)
            return i;
    }
    return -1;
}

Answer 1

由于数组字的长度是常数，这是否意味着该函数在 Big O 表示法中是常数？

Big O 用于描述进程的运行时或内存消耗如何随着其输入的增长而增长。如果您的数组长度是恒定的，那么它将不会增长并产生影响。因此，在此上下文中，您可以考虑在 O（1） 中运行hash()，假设字符串比较是在相对恒定的时间内完成的。

一种思考方式是说，由于数组的长度不是可变的，因此应该总是可以"展开"该循环，以便一个接一个地进行固定数量的 O（1） 比较，总而言之仍然是 O（1）。同样，这假设比较字符串所花费的时间也是恒定的（实际上，如果您有非常大的长度不同的字符串，则情况可能并非如此）。当然，如果你知道数组的内容除了它的长度之外也是常数，那么你可以肯定地说函数将是 O（1）。

Answer 2

比较长度为 m 和 n 的两个字符串所需的时间为 O（min{m， n} + 1）。 假设 k 是 word 数组的长度，m 是 word 中最长单词的长度，n 是输入字符串的长度。 在这种情况下，函数执行 O（k） 字符串比较，每个比较都需要时间 O（min{m， n} + 1）。 因此，运行时为 O（k min{m， n} + m）。

现在，由于已知 m 是一个常数，我们可以简化它并说运行时将是 O（min{m， n} + 1）。 如果 word 中的所有字符串都是固定常量，则 m 是一个常量，运行时为 O（min{1， n} + 1） = O（1），并且哈希函数在常量时间内运行。 否则，如果它们无限长，您唯一可以声称运行时是 O（min{m， n} + 1）。

希望这有帮助！

Answer 3

如果word是常量，则此函数为 O（1）。

s.length() 以恒定的时间运行，而不管 s 的长度如何。

运行word[i].compareTo(s)所需的时间受 word[i] 长度的限制。 只要word不改变，这意味着运行整个 for 循环所需的时间有一个上限。

因此，此函数运行所需的时间有一个上限，该函数为 O（1）。

如果word可以改变，我相信这个函数将是 O（n），其中 n 是 word 的大小。 但是，如果word元素的长度不断增加，则word[i].compareTo(s)将被越来越大的数字所限制，因此s的长度可能开始变得重要。 也许复杂性实际上是 O（n^2）。 我不知道，现在我自己很好奇。

Answer 4

你的函数有复杂度O（N 2），因为它有²个输入：

1. s - 您的字符串（长度 N₁）
2. 字 - 数组（长度 N₂）

所以，你的复杂度将是O（N₁ * N 2），可以简化为O（N₂）

如果长度 N₂ 真的是常量，那么在最坏的情况下，函数的复杂度为 O（N₁）。

如果长度 N 1 也常量 - 那么我们有 O（₁） 复杂度