Естественная сортировка слиянием с минимизацией объема дополнительной памяти
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Естественная сортировка слиянием с минимизацией объема дополнительной памяти
|
|
| Creator |
Винничук, С.Д.
|
|
| Subject |
Вычислительные процессы и системы
|
|
| Description |
Предложен алгоритм, требующий объема дополнительной памяти O (logn), с трудоемкостью в худшем случае O (nlog2 n). Предложены также алгоритмы устойчивой нерекурсивной сортировки слиянием, позволяющие учитывать естественную упорядоченность исходного массива данных длиной n при уменьшении объема дополнительной памяти до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) и трудоемкости в случае наихудшего расположения элементов порядка O (nlogn).
Запропоновано алгоритм, що потребує обсягу додаткової пам’яті O (logn), з трудомісткістю для гіршого випадку O (nlog2 n). Запропоновано також стійкі нерекурсивні алгоритми сортування злиттям, які дозволяють враховувати природню впорядкованість початкового масиву даних довжиною n при зменшенні обсягу додаткової пам’яті до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) з трудомісткістю для гіршого випадку O (nlogn). An algorithm has been proposed, which requires additional memory of the order O (logn) with an estimate of the labour input in the worst case of order O (nlog2n). Variants of resistant nonrecursive merge sorting algorithms have been proposed that take into account the natural ordering of the original data array of length n, with a decrease in the volume of additional memory to the values of n/2 + O (1), n/4 + O (1), n/8 + O (1), and labour input in the worst case of elements location of the order O (nlogn). |
|
| Date |
2014-05-11T15:06:25Z
2014-05-11T15:06:25Z 2011 |
|
| Type |
Article
|
|
| Identifier |
Естественная сортировка слиянием с минимизацией объема дополнительной памяти / С.Д. Винничук // Электронное моделирование. — 2011 — Т. 33, № 6. — С. 33-56. — Бібліогр.: 3 назв. — рос.
0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/61791 004.424.5 : 519.683.6 |
|
| Language |
ru
|
|
| Relation |
Электронное моделирование
|
|
| Publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
|
|