Делает ли использование двух хэш-карт алгоритм O (n в квадрате)?

Question

Я пытаюсь выяснить сложность алгоритма времени и пространства Big O, приведенную ниже.

Я думаю, что сложность времени равна O (n), где n - размер большей HashMap.Насколько я понимаю, что 3 цикла делают его O (3n), но затем вы удаляете константу, чтобы получить O (n).И что HashMaps (по крайней мере в Java) - это O (1) для операций put и get.

Я думаю, что сложность пространства равна O (n), где n - это размер HashMap.

Вот моя проблема, хотя.Есть 2 HashMaps.Итак, это делает сложность пространства nxn = 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) пробел.