Есть ли ниже алгоритм сортировки O (n)? - PullRequest
Новая
       8

Есть ли ниже алгоритм сортировки O (n)?

1 голос
/ 22 февраля 2020

Алгоритм:

  1. вставить количество элементов в карту
  2. начать с первого элемента
  3. , если первый присутствует в карте, вставить в выходной массив (всего число отсчетов), приращение вначале
  4. , если первого нет на карте, найти следующее число, присутствующее на карте

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

vector<int> sort(vector<int>& can) {
    unordered_map<int,int> mp;
    int first = INT_MAX;
    int last = INT_MIN;
    for(auto &n : can) {
        first = min(first, n);
        last = max(last, n);
        mp[n]++;
    }
    vector<int> out;
    while(first <= last) {
        while(mp.find(first) == mp.end()) first ++;
        int cnt = mp[first];
        while(cnt--) out.push_back(first);
        first++;
    }
    return out;
}

1 Ответ

2 голосов
/ 22 февраля 2020

Сложность: O (максимальный элемент в массиве), который является линейным, поэтому O (n).

Нет, это не O (n). while l oop повторяется last - first + 1 раз, и это количество зависит от содержимого массива , а не от длины массива .

Обычно мы используем n означать длину массива, над которым работает алгоритм. Чтобы описать диапазон (т. Е. Разницу между наибольшим и наименьшим значениями в массиве), мы могли бы ввести другую переменную r, а затем сложность по времени составляет O (n + r), поскольку первая l oop заполняет карту повторяет O (n) раз, второй l oop, заполняющий вектор, повторяет O (r) раз, а его внутренний l oop, который отсчитывает от cnt, повторяет O (n) всего раз.

Другим более формальным способом определения n является «размер ввода», обычно измеряемый числом битов, которое требуется для кодирования ввода алгоритма. Предположим, что вход является массивом длины 2, содержащим только числа 0 и M для некоторого числа M. В этом случае, если число битов, используемых для кодирования ввода, равно n, тогда число M может быть порядка O (2 n ), а второй l oop делает это много итераций; поэтому согласно этому формальному определению сложность времени экспоненциальна.

...