Сортировка целых чисел размера 2^n по линейному времени

#algorithm #time-complexity

#алгоритм #временная сложность

Вопрос:

Проблема

Мне нужно разработать алгоритм, который принимает список целых чисел в качестве входных данных и возвращает отсортированный список элементов, которые больше первого log(n) и меньше последнего n - 3 log(n) (другими словами, мне нужен отсортированный список 2log(n) элементов). Целые числа массива находятся в диапазоне от 0 до 2 ^ n. Они должны быть отсортированы за линейное время O(n) , где n — количество элементов во всем списке. Тот факт, что нам нужно только подмножество отсортированных элементов, может иметь отношение к поиску решения, но я не нашел его взаимосвязи.

Мои решения

Я попробовал два решения.

Использование подсчета сортировки, но это приводит к экспоненциальной ( 2^n ) временной и пространственной сложности
Используя сортировку по основанию, но это приводит к квадратичной временной сложности. Это связано с тем, что T(n) = O(d*(n b)) = O(log_b(2^n)*(n b)) = O(n * log_b(2) * (n b)) = O(n^2) независимо от значения b.

Как вы можете видеть, я немного запутался в том, что делать дальше. Заранее спасибо!

1. Да, это означает O (n) временную сложность

2. Пожалуйста, добавьте к вопросу а) что такое n (количество входных чисел как мера размера проблемы?) б) какую модель машины использовать — с ОЗУ вам нужно было бы «исправить» размер регистра, обычно в O (log n).

3. а) Я добавил n как количество элементов в массиве б) ммм, я не понимаю, что вы имеете в виду под типом машины… вы должны предположить, что это теоретическая проблема. Я не думаю, что машина имеет отношение к решению.

4. n-logn-(n-3logn)=2logn, а не n-4logn

5. @polmonroig Всего у вас есть n числа. Из них вы вычитаете первые logn и последние n-3logn числа ==> У вас остаются n-logn-(n-3logn)=2logn числа. По крайней мере, это то, что вы написали.

Ответ №1:

Заслуга SomeWittyUsername заключается в исправлении исходных требований к вопросу.

«Больше первого логарифма (n) и меньше последних n — 3 логарифмических (n) элементов».

Найдите log(n) число th и (n - 3*log(n)) число th с O(n) помощью быстрого выбора.

Отфильтруйте список, чтобы удалить log(n) n - 3*log(n) = n - 2*log(n) элементы.

Теперь у нас n - (n - 2*log(n)) = 2*log(n) есть элементы с диапазоном 2^n .

Сортировка O(log(n)) элементов путем сравнения сортировка требует O(log(n) * log(log(n))) << O(n) времени.