Разрядность ключей при оценке сложности сортировки

[_hum_]

Пролистав источники по методам сортировки и оценке их вычислительной сложности, как-то не заметил, чтобы явно оговаривалось, является ли множество ключей ограниченным или нет. Ведь, если это множество не ограничено, к сложности должна добавляться сложность доступа к ключу, которая пропорциональна его разрядности. Может ли кто-нибудь прояснить ситуацию?

[Circiter]

Я так понимаю, для сортировки нужно отношение частичного порядка и при оценке сложности просто подразумевают, что вычисление этого отношения требует $\mathcal{O}(1)$ ресурсов. Если в вашем алгоритме сортировки приходится сравнивать сортируемые значения не за константное время, скажем за линейное, то придется внести соответсвующую поправку в результирующую асимптотику, например, для линейной сложности сравнения придется приписать множитель $n$ в аргументе $\mathcal{O}(\cdot)$ для такого алгоритма... Пример: наивная сортировка списка строк, реализованная через композицию strcmp() и qsort().

Кстати, очень боюсь, что попросту вас не понял. Мне незнакомо понятие "ключа" в данном контексте... Поясните, пожалуйста.

[_hum_]

Ключ - это то значение, по которому упорядочивается список.

Так, получается, все-таки в общем случае нужно учитывать размер ключа? И кстати, ведь не только при сравнении может тратиться время, но и при операциях обмена наподобие $swap(a_i,a_j)$, которая часто в стандартных алгоритмах сортировок используется. Почему же об этом везде умалчивается...

Единственное упоминание нашел в статье Wiki:[url = "http://ru.wikipedia.org/wiki/Алгоритм_сортировки"]Алгоритм_сортировки[/url]
"Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в $\Omega(n\log n)$ сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью $\Omega(n\log \log n \cdot \log\log \log n)$, использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике)."

Из написанного как бы следует, что в остальных случаях предположение об ограниченности ключей не используется...

[Circiter]

2_hum_

Цитата:

не только при сравнении может тратиться время, но и при операциях обмена

Ну бросьте, обмен бесплатен, $\mathcal{O}(1)$. :) Т.е., достаточно обменивать местами указатели, а не копировать сами сортируемые данные.

Цитата:

Из написанного как бы следует, что в остальных случаях предположение об ограниченности ключей не используется...

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

В обычных же алгоритмах, как я уже сказал, просто считают сложность сравнений константной и все тут. Вы же подразумеваете, что если множество значений бесконечно, то стоимость сравнения неизбежно больше $\mathcal{O}(1)$. Так то оно так, но лишь в теории. Например, при сортировке вещественных чисел операция $\leqslant$ является константной по времени, хотя само множество значений мысленно считают бесконечным, совпадающим с математическим $\mathbb{R}$. На деле-же, конечно, с настоящими бесконечными объектами компьютеры работать, вообще говоря, не умеют. :)

То есть, куда-то вас в философию уводит.

[Psw]

_hum_ в сообщении #479592 писал(а):

Пролистав источники по методам сортировки и оценке их вычислительной сложности, как-то не заметил, чтобы явно оговаривалось, является ли множество ключей ограниченным или нет. Ведь, если это множество не ограничено, к сложности должна добавляться сложность доступа к ключу, которая пропорциональна его разрядности. Может ли кто-нибудь прояснить ситуацию?

Читайте классику - Д.Кнут, Искусство программирования для ЭВМ, том 3. Сортировка и поиск.
У него все это есть.
А по поводу ограниченности - если ограниченно количество уникальных ключей, причем в памяти можно разместить соответствующее кол-во счетчиков, то просто метод подсчета, порядок $O(n)$

[_hum_]

2Circiter

Цитата:

Ну бросьте, обмен бесплатен, . :) Т.е., достаточно обменивать местами указатели, а не копировать сами сортируемые данные.

Точно? Ведь если работать через указатели, то появляется дополнительная емкостная сложность (для их хранения), которая $\Omega(n\log n)$. Тогда как в той же ангоязычной статье с Вики про методы сортировки описывается множество алгоритмов, которые задействуют обмен, но при этом их емкостная сложность равна $O(1)$ [см. табличку http://en.wikipedia.org/wiki/Sorting_algorithm].

Цитата:

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

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

Цитата:

В обычных же алгоритмах, как я уже сказал, просто считают сложность сравнений константной и все тут.

Ясно. Просто нигде в явном виде я этого не встретил, оттого и возник вопрос.

Цитата:

На деле-же, конечно, с настоящими бесконечными объектами компьютеры работать, вообще говоря, не умеют. :)

С бесконечными - да, но никто не запрещает им работать с конечными, но сколь угодно близкими к бесконечным.

Цитата:

То есть, куда-то вас в философию уводит.

Наоборот, в практику. Допустим, будет у кого-то задача, связанная с сортировкой in place больших (не помещающимися в разрядность процессора) чисел. И не знай он этих ньюансов, возьмет и прикинет по "общеизвестной" формуле $O(n\log n)$ для пирамидальной сортировки порядок времени выполнения. Окажется, доли секунды. Он обрадуется и начнет реализацию проекта. А на деле что? На деле он столкнется с тем, что время может стать существенно больше - придется тратить дополнительное время на пересылку, которое $\Omega(k)$, где $k$ - разрядность числа.

2Psw
Из Кнута:
"Программы для компьютера MIX будут, как правило, написаны в предположении, что ключ - числовой и что он помещается в одном слове; иногда мы даже будем ограничивать значения ключей так, чтобы они занимали лишь часть слова.[...] Вместе с программами для MIX приводится анализ времени выполнения соответствующего алгоритма сортировки."

То есть, все-таки получается, что при оценке сложности считается, что множество ключей ограничено. Верно?

[Circiter]

2_hum_

Цитата:

если работать через указатели, то появляется дополнительная емкостная сложность (для их хранения)

Ну и что. Обычный оверхед при работе со связанными списками вместо массивов. Сложность $\mathcal{O}(n)$ по памяти, $n$ - размер выборки. В асимптотической записи это даст только неявный коэффициент.

Цитата:

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

Именно! Более того, такая ограниченность есть следствие асимптотической константности сравнений. О самой ограниченности никто и не думает, вы же сами сказали "никто не запрещает им работать с конечными, но сколь угодно близкими к бесконечным". :)

Цитата:

На деле он столкнется с тем, что время может стать существенно больше

Опять же, ну и что (кстати, все равно выхода-то не будет :) ). Ваше $k$ обычно полагают "фиксированным" (cf. запись в файле БД) и растет оно очень медленно с ростом $n$ и в асимптотической нотации особой погоды не делает. Как-то так... Да и вообще, вы, похоже, путаете асимптотическую производительность с фактической, замеренной в количестве физических операций или требуемого физического времени (при оценке настоящей производительности, да, есть определенные проблемы, в полном соответствии с вашими опасениями).

[_hum_]

Circiter в сообщении #479825 писал(а):

Цитата:

если работать через указатели, то появляется дополнительная емкостная сложность (для их хранения)

Ну и что. Обычный оверхед при работе со связанными списками вместо массивов. Сложность $\mathcal{O}(n)$ по памяти, $n$ - размер выборки. В асимптотической записи это даст только неявный коэффициент.

Наверное, все-таки $\Omega(n \log n)$, ведь разрядность указателей тоже будет расти с ростом $n$ как $\Omega(\log n)$. И в асимптотической записи это не превратится в коэффициент, так как это отдельная сложность - по емкости, и никак не складывается с временной (ведь, по сути, она имеет совсем другую размерность). Обычно пишут - такая-то сложность по времени и такая-то по объему.

Цитата:

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

Я полагал, что "асимтотическая производительность" - это грубая оценка именно "фактической". Иначе, какой смысл во всех этих оценках.

[Circiter]

2_hum_

Цитата:

разрядность указателей тоже будет расти

Нонсенс. Фантастика.

Цитата:

Обычно пишут - такая-то сложность по времени и такая-то по объему.

Когда я говорил "по памяти" я это и имел ввиду, по объему, по пространству. Понимаете? Не усложняйте. :)

Цитата:

Я полагал, что "асимтотическая производительность" - это грубая оценка именно "фактической".

Асимптотическая производительность описывает поведение на бесконечности $n\to\infty$. См. также эту тему.

[_hum_]

Circiter в сообщении #479852 писал(а):

Цитата:

разрядность указателей тоже будет расти

Нонсенс. Фантастика.

Контраргументы? Если Вам требуется хранить указатели на $n$ элементов, то Вам потребуется обеспечить возможность принимать указателями по крайней мере $n$ различных значений, а для этого нужно, чтобы указатели имели по крайней мере $\log n$ разрядов. Что неправильно?

Цитата:

Цитата:

Обычно пишут - такая-то сложность по времени и такая-то по объему.

Когда я говорил "по памяти" я это и имел ввиду, по объему, по пространству. Понимаете? Не усложняйте. :)

Я тоже имел в виду по объему, по пространству. Это ничего не меняет - нельзя ее складывать с временной сложностью. А значит, при использовании указателей помимо временной $C_{TIME}$ сложности появится еще и емкостная (объемная) $C_{MEMORY}$, которая ни в какой коэффициент не превратится, а останется самой собой - $C_{MEMORY}(n) = \Omega(n\log n)$.

Цитата:

Цитата:

Я полагал, что "асимтотическая производительность" - это грубая оценка именно "фактической".

Асимптотическая производительность описывает поведение на бесконечности $n\to\infty$. См. также эту тему.

Позвольте с Вами не согласится. Она описывает аисмптотику не на бесконечности, а просто "при достаточно больших n". И используют ее, насколько я понимаю, по следующим причинам:
1) не всегда удается получить точные оценки;
2) точные оценки зависят от кучи разных ньюансов, связанных с реализацией алгоритма; с другой стороны при больших $n$ эти ньюансы перестают играть роль, а значит, не имеет смысла их рассматривать;
3) на практике важен в первую очередь порядок сложности и порядок роста сложности.
Поэтому-то вполне резонно ожидать, что при достаточно больших (по сравнению со сложностью операций на какие-то промежуточные манипуляции) $n$ эти асимптотические оценки будут давать достаточно хорошие результаты для порядка реального времени вычисления и скорости его роста.

Извиняюсь, за дотошность.

[Circiter]

2_hum_

Цитата:

Контраргументы?

Вы слишком высоко взлетели. А я всего-лишь имел ввиду обычные указатели, которые 32-х битные (ну или 64-х битные). :)

Цитата:

Я тоже имел в виду по объему, по пространству.

А в чем тогда проблема? Я указал в том посте, что говорю о памяти и дальше весь абзац был об этом. Вы же почему-то считаете, что я должен был перед каждым словом оговариваться, что речь идет не о временной сложности, а о пространственной. :) Вы вот, кстати, даже какие-то обозначения предложили, чтобы различать эти случаи, но, как я понимаю, сложившейся традиции на этот счет нет.

Цитата:

при больших $n$ эти ньюансы перестают играть роль, а значит, не имеет смысла их рассматривать

Наоборот, чем больше выборка данных, тем существеннее становятся потери ресурсов в узких местах алгоритма. Это основной мотив для оптимизации. Асимптотические оценки нужны, чтобы видеть как изменится производительность при изменении размера выборки. Вы видимо имели ввиду $\mathcal{O}(n+n^2)=\mathcal{O}(n^2)$. Это немного другое, см. ниже.

Цитата:

и порядок роста сложности

Это ещё лучшее объяснение, $\mathcal{O}$-нотация показывает как растет время (или занимаемая память) при росте $n$. Мыслить об этом как о поведении на бесконечности полезно для правильного восприятия арифметики над такими выражениями (т.е. когда коэффициенты выбрасываем, основания логарифмов тоже выбрасываем, слагаемое $n$ игнорируем если есть слагаемое $n^2$, и т.д.).

[Dmitriy_M]

_hum_ в сообщении #479592 писал(а):

Пролистав источники по методам сортировки и оценке их вычислительной сложности, как-то не заметил, чтобы явно оговаривалось, является ли множество ключей ограниченным или нет. Ведь, если это множество не ограничено, к сложности должна добавляться сложность доступа к ключу, которая пропорциональна его разрядности. Может ли кто-нибудь прояснить ситуацию?

Ключи - это характеристика данных, а не алгоритма.
Характеристика сортировок основанных на сравнение, является число сравнений от числа данных, но не от представления этих данных.

[Dmitriy_M]

_hum_ в сообщении #479592 писал(а):

Пролистав источники по методам сортировки и оценке их вычислительной сложности, как-то не заметил, чтобы явно оговаривалось, является ли множество ключей ограниченным или нет. Ведь, если это множество не ограничено, к сложности должна добавляться сложность доступа к ключу, которая пропорциональна его разрядности. Может ли кто-нибудь прояснить ситуацию?

С чего это множество ключей будет не ограниченным, если мы сортируем конечное множество элементов.