2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Posted automatically
Сообщение04.10.2016, 22:37 
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Computer Science»

 
 
 
 Re: Время работы алгоритмов
Сообщение04.10.2016, 22:45 
Аватара пользователя
Моя версия.
MestnyBomzh в сообщении #1157347 писал(а):
Так вот, почему задача факторизации тогда такая сложная, что её даже использую при шифровании, а сортировка обычного массива считается столь простой задачей?
Возьмите число типичной разрядности, используемой при шифровании, и попытайтесь отсортировать список такого размера. :mrgreen: Это говорит о том, что при соизмеримых $n$ факторизация таки проще.

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

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

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

 
 
 
 Re: Время работы алгоритмов
Сообщение04.10.2016, 22:59 
Аватара пользователя
MestnyBomzh в сообщении #1157347 писал(а):
Однако нет еще линейного алгоритма.

В любой естественной сортировке (основанной на сравнениях) для упорядочивания массива требуется как минимум $n\log n$ сравнений. Поэтому линейной сложности быть не может.
MestnyBomzh в сообщении #1157347 писал(а):
Её вычислительная сложность, как я понимаю, $O(\sqrt{n})$

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

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

 
 
 
 Re: Время работы алгоритмов
Сообщение04.10.2016, 23:07 
MestnyBomzh в сообщении #1157347 писал(а):
Как известно, есть очень много алгоритмов сортировки, все они различные по скорости. Однако нет еще линейного алгоритма.
А теперь рассмотрим другую задачу: задача факторизации целого числа. Её вычислительная сложность, как я понимаю, $O(\sqrt{n})$. Этот алгоритм даже быстрее, чем линейный! Так вот, почему задача факторизации тогда такая сложная, что её даже использую при шифровании, а сортировка обычного массива считается столь простой задачей?
Сложность сортировки $O(n\log n)$, где $n$ - размер входных данных - количество элементов.
В вашей формуле сложности факторизации $n$ - значение самого числа, при этом размер входных данных - $\log n$. Т.е. если вашу формулу переписать, взяв, как это принято, в качестве аргумента размер входных данных, то сложность факторизации получится $O(2^n)$.

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

 
 
 
 Re: Время работы алгоритмов
Сообщение05.10.2016, 18:36 
Аватара пользователя
svv в сообщении #1157360 писал(а):
Но подставив в формулу сложности вместо $n$ выражение $2^k$,

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

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

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

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

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

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

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

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

 
 
 
 Re: Время работы алгоритмов
Сообщение05.10.2016, 22:40 
Аватара пользователя
MestnyBomzh
Цитата:
Во-первых, размер входных данных = кол-во цифр?

Да.


MestnyBomzh в сообщении #1157563 писал(а):
Как я вижу, многие пишут о том, что на самом деле сложность факторизации экспотенциальна. Пока что не могу этого понять, почему?

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

 
 
 
 Re: Время работы алгоритмов
Сообщение06.10.2016, 00:49 
Аватара пользователя

(занудство)

slavav в сообщении #1157620 писал(а):
Первый: если единственной разрешенной операцией является <, то задача сортировки неразрешима быстрее чем за $N\log N$, где $N$ число элементов массива.
Если можно только сравнивать элементы, то отсортировать массив вообще нельзя, т.к. их еще надо переставлять.

 
 
 
 Re: Время работы алгоритмов
Сообщение06.10.2016, 01:09 

(занудство)

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

 
 
 [ Сообщений: 21 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group