Оценка сложности алгоритмов

[@aleks_raiden]

Хорошая статья, спасибо. Когда учился в аспирантуре, была у меня идея научной работы, связанной со сложностью алгоритмов. Хотелось посчитать сложности алгоритмов кодирования информации (разной — в смысле и Jpeg и другие) и алгоритмов низкого уровня хранения (то есть как записано на носитель) чтобы понимать и оценить устойчивость информации к восстановлению в будущем. ТО есть — чем сложнее алгоритм, то даже если он записывает так, что не повреждается ничего и устойчив к потере, например, 50% информации — но он очень сложен и требует M знаний для расшифровки, то его применимость для долговременного (вечного) сохранения информации человечества уменьшается. немного сумбурно, но вот )

[@Krofes]

Есть несколько замечательных книг М.В. Ульянова, там в т.ч. затрагивается и тема оценки вычислительной сложности алгоритмов.
В частности, там описан метод получения оценки временных затрат на выполнение алгоритма от размера данных. Были весьма забавные результаты, вплоть до почти 100%-го попадания прогнозируемого времени выполнения в реальное :)

[@Pand5461]

Что у вас с терминологией?
O-большое, Ω и Θ — это не оценки для худшего, лучшего и среднего случаев. В теории алгоритмов это называют оценками сверху, снизу и асимптотически точной оценкой.

С размером входа вы тоже нас путаете. Википедия говорит, что

под размером входа понимается длина описания данных задачи в битах

Т.е. размер входа задачи вычисления факториала числа n — это [log₂n]+1.

[@potapuff]

Не соглашусь, по поводу «размера входа». Чаще всего алгоритмы оперируют с цепочками (неважно объектов, цифер, чисел, символов или строк) определенной дины. Их внутренне представление чаще всего игнорируется. И n — длина цепочки, а не размер байт, необходимый для ее представления.

[@Pand5461]

А в случае цепочки её длина и число байт, необходимое для её представления — величины пропорциональные, поэтому на асимптотику это не влияет, в О(n) будет меняться только константа.
В случае, когда алгоритм работает с фиксированным количеством численных аргументов, за размер входа естественно взять именно число разрядов в числе, взять хотя бы те же алгоритмы быстрого умножения.
Вычисление факториала — вообще плохой пример для демонстрации вычислительной сложности. Для больших аргументов там нужно учитывать машинное представление ответа. Если же рассматривать только те аргументы, для которых ответ не выходит за пределы 64-битного слова, то вычисление можно организовать за O(1), просто имея в памяти заранее таблицу значений.

[@qw1]

А в случае цепочки её длина и число байт, необходимое для её представления — величины пропорциональные, поэтому на асимптотику это не влияет, в О(n) будет меняться только константа.

Это привычно, но что-то я запутался, покопавшись поглубже.

Пусть n — байтовая длина цепочки, m=8*n — битовая длина.
Сложность алгоритма в байтовой длине f(n)=2^n, или переходя к битовой длине g(m)=2^(8*m).
Не существует никакой константы С, такой что C*f(x) >= g(x) начиная с некоторого x >= x0
Таким образом, O-оценки для f и g различны?

[@Pand5461]

Пусть n — байтовая длина цепочки, m=8*n — битовая длина.
Сложность алгоритма в байтовой длине f(n)=2^n, или переходя к битовой длине g(m)=2^(8*m).
Не существует никакой константы С, такой что C*f(x) >= g(x) начиная с некоторого x >= x0

Вы правы, что-то я не учел, что при экспоненциальной сложности будет не просто домножение на константу при изменении «размерности». Получается, для f и g будут разные асимптотически точные оценки.
И вообще, выходит, для экспоненциальной сложности трудно дать Θ-оценку, т.к. даже небольшая прибавка к показателю степени может давать большой вклад. К примеру, exp(n+log(n))=n*exp(n)≠Θ(exp(n)).

[@hombre]

алгоритма вычисление факториала
for (i = 2; i <= n; i++)
result = result * n;

небольшая опечатка: на i надо умножать )

[@qmax]

Весь стэндфорский курс www.coursera.org/course/algo одной статьёй!