|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Kukushkin 2:5025/37.216 05 Aug 2002 18:44:46
To : Dmitriy K.
Subject : сортировка с линейной сложностью
--------------------------------------------------------------------------------
Понедельник Август 05 2002 в 16:39 Dmitriy K. писал Roman Kukushkin:
RK>> 3) для каждого сегмента выполняем сортировку любым методом;
DK> ^^^^^^^^^^
DK> Любым? Чтобы линейность оставалась для всего, на этом шаге также
DK> должна быть линейность. Опять приходим к поиску линейного алгоритма.
DK> Если же рекурсивно - то получается опять же нелинейно (кажется,
DK> N*log(n) - в книжке об этом подробнее написано).
Я считаю, что среднее куба числа элементов в одном сегменте будет конечным.
Поэтому допустимо использовать например пузырьковую сортировку. Сортировок хуже
пузырьковой я просто не знаю.
DK>>> Зависит от того, что за "данные" и что за "величина".
RK>> Внимательнее читай текст письма, на которое отвечаешь.
DK> Hу и что же я упустил? Фраза "случайная величина с равномерным
DK> распределением" в исходном письме ничего не говорит ни о структуре
DK> самих данных, ни о подходящем и выбранном программистом типе данных.
Когда я пишу алгоритм, мне намного проще, пока я не наткнулся на вычислительную
неустойчивость (чего в задаче сортировки быть не может) или на нехватку памяти,
считать, что вещественный тип полностью эквивалентен вещественному в математике.
До отладки программы очень редко возникает необходимость рассматривать различие
между вещественными числами и машинными вещественными типами. Я думаю, здесь не
будет разницы при использовании типов real, double, extended. Hу а если кто
решил свой тип описывать, пусть он за его поведение и отвечает.
DK> Это может быть и целое число, представляемое типами от byte до int64,
Давай определимся. Я считаю равномерным распредление, при котором случайная
величина может принимать значения из какого-то промежутка [a,b], причем
вероятность попадания в любой промежуток [c,d]\in[a,b] зависит только от длины
этого промежутка. А ты?
DK> или действительное, представляемое теми же float, double, а при
DK> особой изворотливости и целочисленными типами, или строка
DK> какая-нибудь... Так что, как говориться, "Внимательнее читай текст
DK> письма, на которое отвечаешь".
Таки не понял, а я что просмотрел?
C уважением, Roman Kukushkin.
E-mail krv@vudor.vrn.ru
---
* Origin: (2:5025/37.216)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
сортировка с линейной сложностью