java - 使用两个散列图是否使算法 O(n 平方)？

Question

我正在尝试计算以下算法的 Big O 时间和空间复杂度。

我认为时间复杂度是 O(n)，其中 n 是较大的 HashMap 的大小。我的理解是 3 个循环使它成为 O(3n)，但随后你删除常量以获得 O(n)。并且 HashMap(至少在 Java 中)对于 put 和 get 操作是 O(1)。

我认为空间复杂度是 O(n)，其中 n 是 HashMap 的大小。

不过这是我的问题。有 2 个 HashMap。那么，这会使空间复杂度 n x n = n 平方吗？

或者是 O(2n)，变成 O(n)？

HashMap<String,Integer> magazineWordOccurrences = new HashMap<String, Integer>();
for (int i = 0; i < magazine.length; i++)
{
    if (magazineWordOccurrences.containsKey(magazine[i]))
    {
        magazineWordOccurrences.put(magazine[i], magazineWordOccurrences.get(magazine[i]) + 1);
    }
    else
    {
        magazineWordOccurrences.put(magazine[i], 1);
    }
}

HashMap<String,Integer> noteWordOccurrences = new HashMap<String, Integer>();
for (int i = 0; i < note.length; i++)
{
    if (noteWordOccurrences.containsKey(note[i]))
    {
        noteWordOccurrences.put(note[i], noteWordOccurrences.get(note[i]) + 1);
    }
    else
    {
        noteWordOccurrences.put(note[i], 1);
    }
}

boolean match = true;
for (String key: noteWordOccurrences.keySet())
{
    if (magazineWordOccurrences.containsKey(key))
    {
        if (!(magazineWordOccurrences.get(key) >= noteWordOccurrences.get(key)))
        {
            match = false;
            System.out.println("No");
            break;
        }
    }
    else
    {
        match = false;
        System.out.println("No");
        break;
    }
}

if (match)
{
    System.out.println("Yes");
}

Answer 1

有两个HashMap也没关系。

重要的是你有 3 个循环，它们不是嵌套的。每个循环的迭代需要常数时间，因此每个循环的整个运行时间取决于迭代次数。

因此总运行时间为 O(n)，其中 n 是 magazine.length、note.length 和 noteWordOccurrences.keySet().size().

空间复杂度也是线性的，只要你有恒定数量的数据结构(在你的例子中是 2 个 Map)并且每个都需要 O(n)空格。