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

From

Sergey Andrianov (2:5020/1507.400)

To

Dmitriy K.

Date

2002-08-09T23:35:54Z

Area

RU.ALGORITHMS

Здравствуй, Dmitriy!

Однажды 05-Aug-02  в 16:39   Dmitriy K. (via gate)
написал       Sergey Andrianov    по поводу
-=-   Re: сортировка с линейной сложностью  -=-


SA>>    Сортировка с линейной сложностью возможна лишь в случае, когда
SA>> данные могут принимать конечное число значений.

DK> Хм. А когда они принимают не конечное число значений?

Kак известно, даже рациональных чисел на отрезке [0..1] достаточно много. А вещественных - и того больше.

DK> Имхо, тут вопрос в том, жалко ли памяти под линейный алгоритм.

Если мы рассматриваем абстрактный алгоритм, то сталкиваемся с самой настоящей бесконечностью. Если же рассматриваем конкретную компьютерную реализацию, то сталкиваемся с эффективной бесконечностью, т.е. ситуацией, когда конечное число возможных значений сортируемых данных в машинном представлении существенно превосходит адресное пространство (т.е. всегда, когда разрядность сортируемых данных превосходит разрядность адреса).

                  До свидания,  в  23:31 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)