|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : George Shuklin 2:5030/1377 13 Jun 2001 09:04:36
To : All
Subject : Hетривиальная задача
--------------------------------------------------------------------------------
Тут мне в голову пришла не совсем тривиальная задача.
Итак, пусть нам дан массив данных состоящий из двух элементов int. И пусть этот
массив такой, что в память в 2х экземлярах не влазит ни при каких условиях.
Скажем, 3Gb.
Задача. Отсортировать элементы массива таким образом, чтобы сумма времени
сортировки по первому _или_ по второму полю была минимальна.
Поясняю:
Можно отсортировать массив по первому полю. Тогда по второму оно будет больше,
чем из несортированного (предопогаем, что поля независимы и случайно заполнены).
Ищется такое расположение элементов, что время сортировки исходного массива по
первому полю и время сортировки исходного массива по второму полю было
минимальным).
Использовать ссылки, неэкономично - ссылка будет занимать столько же, сколько и
строка массива.
Есть одно решение - перебор. Hо для массивов такого размера это явно не лучшее
решение.
Идеи?
wBL, George. http://nge.narod.ru
--- [team Любовь цвета Hеба] ---
* Origin: Hаскальная манга (2:5030/1377)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
