Время работы алгоритмов

[MestnyBomzh]

Как известно, есть очень много алгоритмов сортировки, все они различные по скорости. Однако нет еще линейного алгоритма.
А теперь рассмотрим другую задачу: задача факторизации целого числа. Её вычислительная сложность, как я понимаю, $O(\sqrt{n})$. Этот алгоритм даже быстрее, чем линейный! Так вот, почему задача факторизации тогда такая сложная, что её даже использую при шифровании, а сортировка обычного массива считается столь простой задачей?

[grizzly]

MestnyBomzh в сообщении #1157347 писал(а):

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

Вы бы это в компьютерном разделе спросили, а не в математическом. Там лучше объяснят. Из общих соображений я думаю, что использовать для шифрования механизмы сортировки массивов принципиально не удобно уже по той причине, что массивы требуют выделения памяти, а не только вычислительных ресурсов -- даже отсортированные. Посчитайте сколько места займёт какой-нибудь массив из $10^{100}$ самых простых элементов. Любые числа в задаче факторизации намного экономичнее.
UPD. Ниже намного лучше объяснили. В подсознании пошёл в нужном направлении, но не осознал до конца :)

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Computer Science»

[svv]

Моя версия.

MestnyBomzh в сообщении #1157347 писал(а):

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

Возьмите число типичной разрядности, используемой при шифровании, и попытайтесь отсортировать список такого размера. Это говорит о том, что при соизмеримых $n$ факторизация таки проще.

Это позволяет раскладывать на множители такие огромные числа $n$, что их размер практически удобнее выражать количеством цифр $k$ (десятичных или двоичных). Но подставив в формулу сложности вместо $n$ выражение $2^k$, Вы получите совсем другую зависимость.

[Pavia]

MestnyBomzh в сообщении #1157347 писал(а):

ак известно, есть очень много алгоритмов сортировки, все они различные по скорости. Однако нет еще линейного алгоритма.
А теперь рассмотрим другую задачу: задача факторизации целого числа. Её вычислительная сложность, как я понимаю, $O(\sqrt{n})$. Этот алгоритм даже быстрее, чем линейный! Так вот, почему задача факторизации тогда такая сложная, что её даже использую при шифровании, а сортировка обычного массива считается столь простой задачей?

Потому, что вы ошибаетесь.

[demolishka]

MestnyBomzh в сообщении #1157347 писал(а):

Однако нет еще линейного алгоритма.

В любой естественной сортировке (основанной на сравнениях) для упорядочивания массива требуется как минимум $n\log n$ сравнений. Поэтому линейной сложности быть не может.

MestnyBomzh в сообщении #1157347 писал(а):

Её вычислительная сложность, как я понимаю, $O(\sqrt{n})$

А относительно длины бинарного представления числа $n$ этот алгоритм экспоненциален. Как и большинство других. Это важно.

Да и как вы собираетесь шифроваться сортировкой?

[venco]

MestnyBomzh в сообщении #1157347 писал(а):

Как известно, есть очень много алгоритмов сортировки, все они различные по скорости. Однако нет еще линейного алгоритма.
А теперь рассмотрим другую задачу: задача факторизации целого числа. Её вычислительная сложность, как я понимаю, $O(\sqrt{n})$. Этот алгоритм даже быстрее, чем линейный! Так вот, почему задача факторизации тогда такая сложная, что её даже использую при шифровании, а сортировка обычного массива считается столь простой задачей?

Сложность сортировки $O(n\log n)$, где $n$ - размер входных данных - количество элементов.
В вашей формуле сложности факторизации $n$ - значение самого числа, при этом размер входных данных - $\log n$. Т.е. если вашу формулу переписать, взяв, как это принято, в качестве аргумента размер входных данных, то сложность факторизации получится $O(2^n)$.

[Евгений Машеров]

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

[MestnyBomzh]

svv в сообщении #1157360 писал(а):

Но подставив в формулу сложности вместо $n$ выражение $2^k$,

demolishka в сообщении #1157368 писал(а):

А относительно длины бинарного представления числа $n$ этот алгоритм экспоненциален. Как и большинство других. Это важно.

venco в сообщении #1157373 писал(а):

$\log n$. Т.е. если вашу формулу переписать, взяв, как это принято, в качестве аргумента размер входных данных, то сложность факторизации получится $O(2^n)$.

Как я вижу, многие пишут о том, что на самом деле сложность факторизации экспотенциальна. Пока что не могу этого понять, почему?
Во-первых, размер входных данных = кол-во цифр?

[Евгений Машеров]

А как хотите, так и меряйте. "Пусть и безобразно, зато однообразно". Просто не путайте, в чём меряете.
Если "размер входа для алгоритма факторизации" это максимально возможное число, то сложность будет $O(\sqrt{n})$, только n это это самое число, которое растёт экспоненциально от длины. А если размер входа это число бит на входе, то, значит, экспонента от числа бит.

[arseniiv]

MestnyBomzh
Мы, конечно, можем представлять числа неэкономно и тратить на это $O(\text{само число})$ памяти, но раз уж так можно не делать… Со списком же сэкономить не получится. Потом, уже упомянули, что неудобно, когда памяти надо кучу занимать.

[slavav]

В теории сложности алгоритмов есть два результата:
Первый: если единственной разрешенной операцией является <, то задача сортировки неразрешима быстрее чем за $N\log N$, где $N$ число элементов массива.
Второй: если набор операций более богатый (скажем, вы можете отобразить элементы в битовые строки с естественной сортировкой), то можно отсортировать за время пропорциональное суммарному числу бит.
Оба результата точные: доказано что быстрее нельзя и приведены примеры алгоритмов, которые работают с этой скоростью.

Что касается оценки факторизации $O(\sqrt{N})$, то $N$ - это величина числа. Такое число займёт $\log N = M$ битов в памяти. Чтобы сравнивать сложности вам надо записать сложноcть от размера числа, а не от его величины: $O(\sqrt{2^M}) = O(2^{\frac{M}{2}})$.

В такой нотации сразу видно, что факторизовать $M$ - битное число намного сложнее, чем отсортировать $M$ - битный массив.

[Pavia]

MestnyBomzh

Цитата:

Во-первых, размер входных данных = кол-во цифр?

Да.

MestnyBomzh в сообщении #1157563 писал(а):

Как я вижу, многие пишут о том, что на самом деле сложность факторизации экспотенциальна. Пока что не могу этого понять, почему?

Откройте учебник по криптографии или к примеру искусство программирования Кнута.

[mihaild]

(занудство)

slavav в сообщении #1157620 писал(а):

Первый: если единственной разрешенной операцией является <, то задача сортировки неразрешима быстрее чем за $N\log N$, где $N$ число элементов массива.

Если можно только сравнивать элементы, то отсортировать массив вообще нельзя, т.к. их еще надо переставлять.

[slavav]

(занудство)

mihaild в сообщении #1157634 писал(а):

Если можно только сравнивать элементы, то отсортировать массив вообще нельзя, т.к. их еще надо переставлять.

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