Найти алгоритм сортировки целых чисел с временной сложностью O (n + k * log (k)) - PullRequest
Новая
       33

Найти алгоритм сортировки целых чисел с временной сложностью O (n + k * log (k))

6 голосов
/ 02 апреля 2020

Разработайте алгоритм, который сортирует n целые числа, где есть дубликаты. Общее количество разных номеров составляет k . Ваш алгоритм должен иметь временную сложность O (n + k * log (k)) . Ожидаемое время достаточно. Для каких значений k алгоритм становится линейным?

Я не могу придумать алгоритм сортировки целых чисел, который удовлетворяет условию, что он должен быть O (n + k * log (k)) . Я не очень продвинутый программист, но у меня была проблема, прежде чем этот должен был придумать алгоритм для всех чисел xi в списке, 0 ≤ xi ≤ m такой, чтобы алгоритм был O (n + m), где n было количество элементов в списке, а m было значением наибольшего целого числа в списке. Я легко решил эту проблему, используя сортировку по счету, но я борюсь с этой проблемой. Самым сложным условием для меня является термин k*log(k) в нотации ordo, если бы он был n*log(n), вместо этого я мог бы использовать сортировку слиянием, верно? Но сейчас это невозможно, поэтому любые идеи будут очень полезны.

Заранее спасибо!

Ответы [ 3 ]

11 голосов
/ 02 апреля 2020

Вот возможное решение:

  • Используя таблицу ha sh, подсчитайте количество уникальных значений и количество дубликатов каждого значения. Это должно иметь сложность O (n) .

  • Перечислять хеш-таблицу, сохраняя уникальные значения во временном массиве. Сложность равна O (k) .

  • Сортировать этот массив с помощью стандартного алгоритма, такого как mergesort: сложность равна O (k.log (k)) .

  • Создайте результирующий массив, реплицировав элементы отсортированного массива уникальных значений, каждое количество раз сохраняемое в таблице ha sh. сложность O (n) + O (k) .

  • Общая сложность O (n + k.log (k)) .

Например, если k - маленькая константа, сортировка массива значений n сходится к линейному времени как n становится все больше и больше.

Если на первом этапе, где k вычисляется постепенно, оказывается, что k не намного меньше, чем n , удалите таблицу ha sh и просто отсортируйте исходный массив стандартным алгоритмом.

0 голосов
/ 02 апреля 2020

Возможное Java решение может быть таким: 

public List<Integer> sortArrayWithDuplicates(List<Integer> arr) {

    // O(n)
    Set<Integer> set = new HashSet<>(arr);

    Map<Integer, Integer> freqMap = new HashMap<>();
    for(Integer i: arr) {
       freqMap.put(i, freqMap.getOrDefault(i, 0) + 1);
    }

    List<Integer> withoutDups = new ArrayList<>(set);

    // Sorting => O(k(log(k)))
    // as there are k different elements
    Arrays.sort(withoutDups);

    List<Integer> result = new ArrayList<>();

    for(Integer i : withoutDups) {
        int c = freqMap.get(i); 
        for(int j = 0; j < c; j++) {
            result.add(i);
        }
    }

    // return the result
    return result; 
}

Временная сложность приведенного выше кода составляет O(n + k*log(k)), и решение находится в той же строке, что и ответ на вопрос выше.

0 голосов
/ 02 апреля 2020

Время выполнения O(n + k*log(k) указывает (как часто бывает при добавлении во время выполнения), что у вас есть 2 подпрограммы, одна из которых запускается в O(n), а другая - в O(k*log(k)).

  1. Сначала вы можете считать частоту элементов в O(n) (например, в Hashmap , посмотрите это, если вы не знакомы с ним, это очень полезно).

  2. Затем вы просто сортируете уникальные элементы, из которых есть k. Эта сортировка выполняется в O(k*log(k)), используйте любой алгоритм сортировки, который вы хотите.

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

...