сортировка с линейной сложностью

From

Roman Kukushkin (2:5025/37.216)

To

Dmitriy K.

Date

2002-08-05T18:44:46Z

Area

RU.ALGORITHMS

Как поживаете, Dmitriy ?

 Понедельник Август 05 2002 в 16:39 Dmitriy K. писал Roman Kukushkin:

 RK>> 3) для каждого сегмента выполняем сортировку любым методом;
 DK>                                        ^^^^^^^^^^

 DK> Любым? Чтобы линейность оставалась для всего, на этом шаге также
 DK> должна быть линейность. Опять приходим к поиску линейного алгоритма.
 DK> Если же рекурсивно - то получается опять же нелинейно (кажется,
 DK> N*log(n) - в книжке об этом подробнее написано).
Я считаю, что среднее куба числа элементов в одном сегменте будет конечным.
Поэтому допустимо использовать например пузырьковую сортировку. Сортировок хуже пузырьковой я просто не знаю.

 DK>>> Зависит от того, что за "данные" и что за "величина".
 RK>> Внимательнее читай текст письма, на которое отвечаешь.

 DK> Ну и что же я упустил? Фраза "случайная величина с равномерным
 DK> распределением" в исходном письме ничего не говорит ни о структуре
 DK> самих данных, ни о подходящем и выбранном программистом типе данных.
Когда я пишу алгоритм, мне намного проще, пока я не наткнулся на вычислительную неустойчивость (чего в задаче сортировки быть не может) или на нехватку памяти, считать, что вещественный тип полностью эквивалентен вещественному в математике. До отладки программы очень редко возникает необходимость рассматривать различие между вещественными числами и машинными вещественными типами. Я думаю, здесь не будет разницы при использовании типов real, double, extended. Ну а если кто решил свой тип описывать, пусть он за его поведение и отвечает.

 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)