Сравнение этих двух алгоритмов?

Поэтому мне предъявлена проблема, которая заявляет. "Определите, содержит ли строка все уникальные символы"

Поэтому я написал это решение, которое добавляет каждый символ в набор, но если символ уже существует, он возвращает false.

private static boolean allUniqueCharacters(String s) {

    Set<Character> charSet = new HashSet<Character>();
    for (int i = 0; i < s.length(); i++) {
        char currentChar = s.charAt(i);
        if (!charSet.contains(currentChar)) {
            charSet.add(currentChar);

        } else {
            return false;
        }

    }
    return true;

}

Согласно книге, которую я читаю, это "оптимальное решение",

public static boolean isUniqueChars2(String str) {
    if (str.length() > 128)
        return false;

    boolean[] char_set = new boolean[128];

    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);

        if (char_set[val]) {
            return false;
        }
        char_set[val] = true;
    }

    return true;
}

Мой вопрос в том, что моя реализация медленнее, чем представленная? Я предполагаю, что это так, но если поиск Хэша будет O (1), не будет ли они такой же сложностью?

Спасибо.

Ответы

Ответ 1

Как сказал Амадан в комментариях, эти два решения имеют одинаковую сложность времени O (n), потому что у вас есть цикл цикла, проходящий через строку, и вы выполняете операции постоянного времени в цикле for. Это означает, что время, затрачиваемое на выполнение ваших методов, линейно увеличивается с длиной строки.

Обратите внимание, что временная сложность - это то, как изменяется время, когда вы изменяете размер ввода. Это не о том, насколько быстро это происходит с данными того же размера.

Для той же строки "оптимальное" решение должно быть быстрее, потому что наборы имеют некоторые накладные расходы по массивам. Обработка массивов выполняется быстрее, чем обработка наборов. Однако, чтобы фактически создать "оптимальное" решение, вам понадобится массив длиной 2 ^ 16. Вот как много разных значений char. Вам также потребуется удалить проверку на строку длиной более 128.

Это один из многих примеров компромисса между пространством и временем. Если вы хотите, чтобы он работал быстрее, вам нужно больше места. Если вы хотите сэкономить место, вам нужно идти медленнее.

Ответ 2

Оба алгоритма имеют временную сложность O (N). Разница заключается в их пространственной сложности.

Решение книги всегда требует хранения для 128 символов - O(1), в то время как ваше пространство для решения будет меняться линейно в соответствии с входом - O(N).

Требование пространства книги основано на предполагаемом наборе символов с 128 символами. Но это может быть довольно проблематичным (и не масштабируемым), учитывая вероятность необходимости использования разных наборов символов.

Ответ 3

Хешмап в теории приемлем, но является отходами.

Хешмап построен над массивом (поэтому он, конечно, дороже, чем массив), а разрешение конфликтов требует дополнительного пространства (по крайней мере, двойного числа элементов). Кроме того, для любого доступа требуется вычисление хэша и, возможно, разрешение столкновений.

Это добавляет много накладных расходов с точки зрения пространства и времени по сравнению с прямым массивом.

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

В качестве заключительного замечания временная сложность этого алгоритма O (1), потому что вы заканчиваете ложь хуже, когда N> 128.

Ответ 4

Ваш алгоритм также O(1). Вы можете подумать о сложности, например, how my algorithm will react to the change in amount of elements processed. Поэтому O(n) и O(2n) эффективно равны.

Люди говорят о нотации в качестве темпов роста здесь

Ответ 5

Ваше решение действительно может быть медленнее, чем решение для книги. Во-первых, хэш-поиск идеально подходит для постоянного поиска времени. Но поиск объекта не будет, если есть несколько столкновений с хэшем. Во-вторых, даже если это постоянный поиск по времени, обычно возникают значительные накладные расходы на выполнение функции хэш-кода по сравнению с поиском элемента в массиве по индексу. Вот почему вы можете пойти с поиском массива. Однако, если вы начнете разбираться с символами Unicode, отличными от ASCII, тогда вы можете не захотеть использовать подход массива из-за значительного объема служебных данных.

Ответ 6

Узким местом реализации является то, что набор имеет сложность поиска (и вставки) O(log k), в то время как массив имеет сложность поиска в O(1).

Это звучит так, будто ваш алгоритм должен быть намного хуже. Но на самом деле это не так, поскольку k ограничено 128 (иначе эталонная реализация будет неправильной и приведет к ошибке за пределами границ) и может рассматриваться как константа. Это делает установочный поиск O(1) также с немного большими константами, чем поиск массива.

* предполагая правильную реализацию как дерево или hashmap. Сложность времени hashmap вообще не постоянна, так как для ее заполнения требуются операции изменения размера log(n) чтобы избежать увеличения коллизий, которые привели бы к линейному времени поиска, см. Здесь здесь и здесь для ответов на stackoverflow.

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