|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 13 Jun 2001 16:19:40
To : George Shuklin
Subject : Re: Hетривиальная задача
--------------------------------------------------------------------------------
Привет! "George Shuklin" <George.Shuklin@f1377.n5030.z2.fidonet.org>
сообщил(а) нам:
> Итак, пусть нам дан массив данных состоящий из двух элементов int. И пусть
этот
> массив такой, что в память в 2х экземлярах не влазит ни при каких
условиях.
> Скажем, 3Gb.
> Задача. Отсортировать элементы массива таким образом, чтобы сумма времени
> сортировки по первому _или_ по второму полю была минимальна.
Простейший вариант - плюнуть на все и сортировать столбцы например
пирамидальной сортировкой (пропорционально O(N*log(N)), кол-во операций
практически не зависит от данных, дополнительной памяти не требуется). В
результате гарантированно получаешь O(N*log(N)).
Второй вариант - если int двухбайтовый. В этом случае может быть только
65536 значений (что во много раз меньше, чем строк в массиве). Можно
использовать технику, используемую в поразрядной сортировке и сократить
кол-во операций до O(N). Правда дополнительная память (и немало) все же
потребуется.
> Можно отсортировать массив по первому полю. Тогда по второму оно будет
больше,
> чем из несортированного (предопогаем, что поля независимы и случайно
> заполнены).
См. выше: пирамидальная сортировка практически не зависит от данных.
С уважением, Андрей.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Hетривиальная задача 