Почему этот код O (n ^ 2) выполняется быстрее, чем O (n)?

Я написал код для двух подходов, чтобы найти первый уникальный символ в строке на LeetCode.

Постановка задачи: По заданной строке найдите в ней первый неповторяющийся символ и верните его индекс. Если он не существует, верните -1.

Примеры тестовых случаев:

s = "leetcode" вернуть 0.

s = "loveleetcode", возврат 2.

Подход 1 (O (n)) (поправьте меня, если я ошибаюсь):

class Solution {
    public int firstUniqChar(String s) {

        HashMap<Character,Integer> charHash = new HashMap<>();

        int res = -1;

        for (int i = 0; i < s.length(); i++) {

            Integer count = charHash.get(s.charAt(i));

            if (count == null){
                charHash.put(s.charAt(i),1);
            }
            else {
                charHash.put(s.charAt(i),count + 1);
            }
        }

        for (int i = 0; i < s.length(); i++) {

            if (charHash.get(s.charAt(i)) == 1) {
                res = i;
                break;
            }
        }

        return res;
    }
}

Подход 2 (O (n ^ 2)):

class Solution {
    public int firstUniqChar(String s) {

        char[] a = s.toCharArray();
        int res = -1;

        for(int i=0; i<a.length;i++){
            if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {
                res = i;
                break;
            }
        }
        return res;
    }
}

В подходе 2, я думаю, сложность должна быть O (n ^ 2), так как indexOf здесь выполняется в O (n * 1).

Но когда я выполняю оба решения на LeetCode, я получаю время выполнения 19 мс для подхода 2 и 92 мс для подхода 1. Я запутался; почему это происходит?

Я предполагаю, что тесты LeetCode для малых и больших входных значений для лучших, худших и средних случаев.

Обновить:

Мне известно о том, что O (n ^ 2 алгоритмов) может работать лучше для определенных n <n1. В этом вопросе я хотел понять, почему это происходит в этом случае. т.е. какая часть подхода 1 делает его медленнее.

LeetCode ссылка на вопрос

Ответы

Ответ 1

Рассматривать:

f ₁ (n) = n ²
f ₂ (n) = n + 1000

Ясно, что f ₁ является O (n ²) и f ₂ является O (n). Для небольшого ввода (скажем, n = 5) мы имеем f ₁ (n) = 25, но f ₂ (n)> 1000.

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

Ответ 2

Для очень коротких строк, например, одного символа, стоимость создания HashMap, изменения его размера, поиска записей при упаковке и распаковке char в Character может затмить стоимость String.indexOf(), которая, вероятно, считается горячей и встроенной в JVM. путь.

Другой причиной может быть стоимость доступа к оперативной памяти. С дополнительными объектами HashMap, Character и Integer включенными в поиск, может потребоваться дополнительный доступ к оперативной памяти и из нее. Одиночный доступ составляет ~ 100 нс, и это может сложить.

Взгляните на Бьярне Страуструпа: почему вы должны избегать связанных списков. Эта лекция иллюстрирует, что производительность не такая же, как сложность, и доступ к памяти может быть убийственным для алгоритма.

Ответ 3

Обозначение Big O представляет собой теоретическую меру того, как алгоритм масштабируется в терминах потребления памяти или вычислительного времени с N - количеством элементов или доминирующих операций, и всегда как N->Infinity.

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

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

На практике с современными архитектурами ЦП, где кэш форм чтения на несколько порядков быстрее, чем в основной памяти, N будет достаточно большим, прежде чем использовать теоретически оптимальный алгоритм, превосходящий линейную структуру данных и линейный поиск. Двоичные деревья являются особенно плохой новостью для эффективности кэширования.

[Edit] it Java: хеш-таблица содержит ссылки на java.lang.Character объект java.lang.Character. Каждое добавление приведет к выделению памяти

Ответ 4

O (n ²) является только наихудшей временной сложностью второго подхода.

Для таких строк, как bbbbbb...bbbbbbbbbaaaaaaaaaaa...aaaaaaaaaaa где есть x b и x a, каждая итерация цикла занимает около x шагов для определения индекса, следовательно, общее количество выполненных шагов составляет около 2x ². Для x около 30000 это займет около 1-2 секунд, в то время как другое решение будет работать намного лучше.

В режиме онлайн, этот тест вычисляет, что подход 2 примерно в 50 раз медленнее, чем подход 1 для приведенной выше строки. Для больших x разница еще больше (заход на посадку 1 занимает около 0,01 секунды, заход на посадку 2 занимает несколько секунд)

Тем не мение:

Для строк с каждым символом, выбранным независимо, равномерно из {a,b,c,...,z} ^[1] ожидаемая сложность по времени должна составлять O (n).

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

Можно легко доказать (доказательство аналогично этому посту на Math.SE - Ожидаемое значение количества показов до первой главы), что ожидаемое положение конкретного символа в единой независимой строке над алфавитом {a,b,c,...,z} есть O (1). Поэтому каждый indexOf и lastIndexOf выполняется за ожидаемое время O (1), а весь алгоритм занимает ожидаемое время O (n).

^[1]: в оригинальном вызове leetcode сказано, что

Вы можете предположить, что строка содержит только строчные буквы.

Однако это не упоминается в вопросе.

Ответ 5

Кароль уже дал хорошее объяснение вашего особого случая. Я хочу добавить общее замечание, касающееся большой буквы O для сложности времени.

В общем, на этот раз сложность не слишком много говорит о реальной производительности. Это просто дает вам представление о количестве итераций, необходимых для конкретного алгоритма.

Позвольте мне сказать это так: если вы выполняете огромное количество быстрых итераций, это все равно может быть быстрее, чем выполнение очень небольшого количества чрезвычайно медленных итераций.

Ответ 6

Во-первых, анализ сложности не говорит вам очень много. Раньше он рассказывал вам, как алгоритмы - теоретически - сравниваются по мере того, как размер проблемы возрастает до больших чисел (к бесконечности, если хотите), и в некоторой степени это все еще происходит.
Тем не менее, анализ сложности делает предположения, которые были лишь наполовину верными около 30-40 лет назад и в настоящее время никоим образом не верны (например, все операции одинаковы, все обращения одинаковы). Мы живем в мире, в котором постоянные факторы огромны, и не все операции одинаковы, даже отдаленно. Насколько это нужно рассматривать с особой тщательностью, ни в коем случае нельзя считать, что "это O (N), поэтому будет быстрее". Это огромная ошибка.

Для небольших чисел смотреть на "большое О" в большинстве случаев бессмысленно, но даже для больших чисел следует помнить, что постоянный фактор может играть огромную доминирующую роль. Нет, постоянный коэффициент не равен нулю, и он не пренебрежимо мал. Никогда не предполагайте это.
Теоретически супер удивительный алгоритм, который, например, находит что-то в миллиарде элементов с только 20 доступами, может быть намного медленнее, чем "плохой" алгоритм, который принимает 200 000 обращений - если в первом случае каждый из 20 доступов вызывает сбой страницы с поиском диска (каждая из которых стоит несколько сотен миллионов операций). Теория и практика здесь не всегда идут рука об руку.

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

O (N ²) один раз преобразует умеренно небольшую строку в массив символов (который в основном стоит ноль), а затем многократно обращается к этому массиву линейным способом. Это самая быстрая вещь, которую может сделать компьютер, даже на Java. Да, Java не зависит от таких вещей, как память или кэши, но это не может изменить тот факт, что эти вещи существуют. Локальный доступ к небольшим/средним объемам данных в основном линейным способом является быстрым.

Другой фрагмент вставляет символы в хэш-карту, выделяя структуру данных для каждого символа. Да, динамическое распределение в Java не так уж и дорого, но, тем не менее, распределение далеко не свободно и доступ к памяти становится несмежным.
Затем вычисляется хеш-функция. Это то, что часто упускается из виду с хэш-картами. Для одного персонажа это (надеюсь) дешевая операция, но она далеко не бесплатная ^[1]. Затем структура данных каким-то образом вставляется в корзину (что технически является ничем иным, как другим некогерентным доступом к памяти). Теперь есть большая вероятность столкновения, и в этом случае нужно сделать что-то еще (цепочка, перефразировка, что угодно).
Позже значения снова считываются из хэш-карты, что снова включает вызов хеш-функции, поиск корзины, возможно, обход списка и сравнение на каждом узле (это необходимо из-за возможности коллизий).

Таким образом, каждая операция включает в себя как минимум две косвенные операции плюс некоторые вычисления. В общем, это ужасно дорого по сравнению с просто повторением небольшого массива пару раз.

^{[1] Здесь} нет проблем с односимвольными ключами, но все же забавный факт: люди часто говорят о хэш-картах в терминах O (1), что уже не соответствует, например, цепочке, но затем удивляются, что на самом деле хеширование ключа равно O (N) относительно длины ключа. Что вполне может быть заметно.

Ответ 7

Я портировал функции на C++ (17), чтобы увидеть, было ли различие вызвано сложностью алгоритма или Java.

#include <map>
#include <string_view>
int first_unique_char(char s[], int s_len) noexcept {
    std::map<char, int> char_hash;
    int res = -1;
    for (int i = 0; i < s_len; i++) {
        char c = s[i];
        auto r = char_hash.find(c);
        if (r == char_hash.end())
            char_hash.insert(std::pair<char, int>(c,1));
        else {
            int new_val = r->second + 1;
            char_hash.erase(c);
            char_hash.insert(std::pair<char, int>(c, new_val));
        }
    }
    for (int i = 0; i < s_len; i++)
        if (char_hash.find(s[i])->second == 1) {
            res = i;
            break;
        }
    return res;
}
int first_unique_char2(char s[], int s_len) noexcept {
    int res = -1;
    std::string_view str = std::string_view(s, s_len);
    for (int i = 0; i < s_len; i++) {
        char c = s[i];
        if (str.find_first_of(c) == str.find_last_of(c)) {
            res = i;
            break;
        }
    }
    return res;
}

Результат был:

Второй - на 30% быстрее для leetcode.

Позже я заметил, что

    if (r == char_hash.end())
        char_hash.insert(std::pair<char, int>(c,1));
    else {
        int new_val = r->second + 1;
        char_hash.erase(c);
        char_hash.insert(std::pair<char, int>(c, new_val));
    }

может быть оптимизирован для

    char_hash.try_emplace(c, 1);

Что также подтверждает, что сложность - не единственное. Есть "длина ввода", которую охватили другие ответы и, наконец, я заметил, что

Реализация также имеет значение. Более длинный код скрывает возможности оптимизации.