Почему O (n ^ 2) быстрее, чем O (n) в отображении анаграммы? - PullRequest
Новая
       15

Почему O (n ^ 2) быстрее, чем O (n) в отображении анаграммы?

0 голосов
/ 15 мая 2018

Учитывая два списка A и B, и B - анаграмма A. B - анаграмма A, означает, что B сделан путем рандомизации порядка элементов в A. Мы хотим найти отображение индекса P, от A до BОтображение P [i] = j означает, что i-й элемент в A появляется в B с индексом j.Эти списки A и B могут содержать дубликаты.

Например, если дано

A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28]. Мы должны вернуть [1, 4,3, 2, 0]

Мое решение - O (n ^ 2) 

public int[] anagramMappings(int[] A, int[] B) {
    int[] result = new int[100];
    int count = 0;
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < B.length; j++) {
            if (A[i] == B[j]) {
                result[i] = j;
                count++;
                break;
            }
        }
    }
    int[] tempArray = new int[count];
    for (int i = 0; i < count; i++) {
        tempArray[i] = result[i];
    }
    return tempArray;
}

Вот еще одно решение, которое, я думаю, более эффективно, чем приведенное выше.Я говорю это, потому что я тестировал оба фрагмента с разными выходами и первый фрагмент почти всегда выполнялся быстрее.

Пожалуйста, поясните, почему первый фрагмент быстрее, чем второй фрагмент.Я считаю, что 2-й более эффективен при сложности O (n) 

public int[] anagramMappingsx(int[] A, int[] B) {
    int[] res = new int[A.length];
    int index = 0;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < B.length; i++) {
        if (!map.containsKey(B[i])) {
            map.put(B[i], i);
        }
    }
    for (Integer i : A) {
        if (map.containsKey(i)) {
            res[index++] = map.get(i);
        }
    }
    return res;
}

1 Ответ

0 голосов
/ 15 мая 2018

Анализ Big-O предполагает, что N очень большое. Речь идет о том, что происходит со сложностью, когда N уходит в бесконечность. Так, например, O (n + 100) совпадает с O (n). Но ясно, что для малых N и больших констант это не так.

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

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

Массивы также, как правило, работают быстрее, чем другие структуры данных, из-за локальности памяти и оптимизации компилятора (хотя это зависит от вашего языка). Локальная память, сокращение выделения / освобождения и устранение динамической диспетчеризации часто оказывают такое же или большее влияние на производительность в реальном мире, чем анализ сложности big-O.

Обидно, что программы CS и интервью на доске так много внимания уделяют анализу Big-O, как будто это начало и конец выступления. Производительность намного больше, чем сложность алгоритма

Если вы хотите, чтобы ваш алгоритм O (n) отбросил ваш алгоритм O (n ^ 2), попробуйте запустить их с элементами 10k или 10M, а не 5. В этих масштабах big-O гораздо более вероятно доминирует ситуация.

...