Сокращение трудоемкости с использованием HashMap или есть лучший способ?

Question

Да, это из более старого экзамена, который я использую для подготовки своего собственного экзамена в январе.Нам дают следующий метод:

public static void Oorspronkelijk()
{
    String bs = "Dit is een boodschap aan de wereld";
    int max = -1;
    char let = '*';
    for (int i=0;i<bs.length();i++) {
        int tel = 1;
        for (int j=i+1;j<bs.length();j++) {
            if (bs.charAt(j) == bs.charAt(i)) tel++;
        }

        if (tel > max) {
            max = tel;
            let = bs.charAt(i);
        }
    }

    System.out.println(max + " keer " + let);
}

Вопросы:

1. каков результат?- Поскольку код является всего лишь алгоритмом для определения наиболее часто встречающегося символа, на выходе получается «6 кеер» (6-кратный интервал)
2. Какова временная сложность этого кода?Совершенно уверен, что это O (n²), если кто-то не думает иначе?
3. Можете ли вы уменьшить сложность времени, и если да, то как?

Ну, вы можете.Я уже получил некоторую помощь и смог получить следующий код:

public static void Nieuw()
{
    String bs = "Dit is een boodschap aan de wereld";
    HashMap<Character, Integer> letters = new HashMap<Character, Integer>();
    char max = bs.charAt(0);
    for (int i=0;i<bs.length();i++) {
        char let = bs.charAt(i);
        if(!letters.containsKey(let)) {
            letters.put(let,0);
        }

        int tel = letters.get(let)+1;
        letters.put(let,tel);

        if(letters.get(max)<tel) {
            max = let;
        }
    }

    System.out.println(letters.get(max) + " keer " + max);
}

Однако я не уверен во временной сложности этого нового кода: это O (n), потому что вы используете только одинfor-loop, или тот факт, что нам требуется использование методов get HashMap, делает его O (n log n)?

И если кто-то знает еще лучший способ уменьшить сложность времени, пожалуйста, сообщите!:)

Answer 1

Временная сложность нового кода - O (n) - это потому, что поиск по хеш-карте является операцией с постоянным временем, и операция с постоянным временем не влияет на порядок.

Одно предложение, которое я мог бы сделать, простохотя оптимизация (не будет иметь большого значения) - не главное изменение и не повлияет на порядок - в том, что вы можете использовать массив целых, а не хеш-карту для отслеживания количества каждого символа.Просто используйте значение int, эквивалентное char, в качестве индекса массива.

Answer 2

Hashmap - это O (1), но здесь вы также можете использовать массив, так как количество букв довольно мало (всего 256), вы также можете использовать массив.Это также O (1), но он быстрее, использует меньше памяти и проще:

String bs = "Dit is een boodschap aan de wereld";
int letters[] = new int[256];
char max = 0;
for (int i=0;i<bs.length();i++) {
    char let = bs.charAt(i);
    ++letters[let];

    if(letters[max] < letters[let]) {
        max = let;
    }
}

System.out.println(letters[max] + " keer " + max);

Answer 3

Чтобы гарантировать, что HashMap всегда будет иметь временную сложность O (1), вам, возможно, придется ввести надлежащий initialCapacity. Вам нужно знать полные значения домена, которые будет иметь bs String.

Если предположить, 1. Как верхний, так и нижний регистры будут рассматриваться отдельно. 2. Строка будет содержать только алфавиты и символ пробела

Начальная грузоподъемность должна быть больше, чем 26 (нижний регистр) + 26 (верхний регистр) + 1 (пробел) = 53

53 + 25% (53) = 53 + 13,25 + 2,75 (буфер) = 69.

Таким образом, инициализация hashmap может быть такой, как показано ниже,

HashMap letters = new HashMap (69);

Answer 4

Я думаю, что это O(n). потому что поиск в HashMap просто O(1)

for (int i=0;i<bs.length();i++) { // O(n)
    char let = bs.charAt(i); // O(1)
    if(!letters.containsKey(let)) { // O(1)
        letters.put(let,0);
    }

общая сложность O(n)

Answer 5

Операция get для хеш-функции равна O (1), поэтому сложность времени вашего решения равна O (n).Вы не можете добиться большего успеха, чем это, поскольку любое решение потребовало бы, чтобы вы прочитали весь ввод хотя бы один раз.