|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 09 Aug 2002 23:35:54
To : Dmitriy K.
Subject : Re: сортировка с линейной сложностью
--------------------------------------------------------------------------------
Однажды 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
