2

我有一个散列函数，我想知道它是否是常数。由于数组字的长度是恒定的，这是否意味着函数在大 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;
}
4

4 回答 4

1

由于数组字的长度是恒定的，这是否意味着函数在大 O 表示法中是恒定的？

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

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

于 2013-10-11T19:56:22.037 回答
0

比较两个长度为 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)。

希望这可以帮助！

于 2013-10-11T19:56:49.263 回答
0

您的函数复杂度为 O(N 2 )，因为它有 2 个输入：

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

因此，您的复杂度将是 O(N 1 *N 2 )，可以简化为 O(N 2 )

如果长度 N 2真的是 const，那么函数在最坏的情况下将具有 O(N 1 ) 的复杂度。

如果长度 N 1也是 consts - 那么我们有 O(1) 复杂度

于 2013-10-11T19:57:39.407 回答
0

如果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)。我不知道，现在我自己很好奇。

于 2013-10-11T20:03:39.903 回答