Вычислительная сложность алгоритмов

[Cubic]

Добрый день.

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

Заранее благодарю.

[bin]

М. Гэри, Д. Джонсон: Вычислительные машины и труднорешаемые задачи - это "библия" теоретиков, но м.б. у Вас сугубо практический случай? Тогда надо ставить вопрос не о сравнении алгоритмов, а о сравнении их реализаций, т.е. программ. Тем более, если это задача реального времени. М.б.:
Первозванский А. А. Курс теории автоматического управления. М., Наука, 1986
Поляк Б. Т., Щербаков П. С. Робастная устойчивость и управление. М., Наука, 2002
Или в сетке поиск сделать, нпр.:
http://www.mathworks.com/products/control/ -- Control System Toolbox for design and analysis of control systems.

[Zealint]

Ответ на Ваш вопрос едва ли отыщется в книге. Вам нужно брать и тестировать, тестировать, тестировать... пока не надоест. Когда надоест, это ещё будет только половина работы. Мне неоднократно приходилось видеть то, как на разных устройствах разные алгоритмы (их реализации) давали совершенно непредсказуемые и никак теоретически не выводимые результаты. При распараллеливании время от времени даже нарушался закон Амдала (что для теоретиков просто немыслимо). Предварительную же оценку работоспособности чего-либо следует проводить из опыта, а не книжек четвертьвековой (и даже десятилетней) давности.

Это я к тому, что обосновать строго ситуацию

Цитата:

Лучший результат у самого медленного алгоритма, худший -- у самого простого и быстрого.

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

[Cubic]

2 bin
Спасибо за ссылку на литературу. Вы правы -- мне нужно оценить конкретные реализации (мои собственные) алгоритмов. Я сейчас читаю "Лекции о сложности алгоритмов", С.А. Абрамов. Вроде это то, что мне нужно.

Zealint

Цитата:

Предварительную же оценку работоспособности чего-либо следует проводить из опыта

Это у меня уже есть. Я точно знаю что Алгоритм 3 быстрее Алгоритма 2, Алгоритм 2 быстрее Алгоритма 1. Время исполнения алгоритма брал из MATLABа.

Цитата:

При распараллеливании время от времени даже нарушался закон Амдал

Над этим мне тоже нужно будет поработать.

Цитата:

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

У меня, вроде, не все так плохо - я могу зафиксировать конкретную платформу. Но это на втором этапе. На первом этапе мне нужно оценить сложность отдельно взятого алгоритма, для фиксированного входа. Думаю, что "Лекции о сложности алгоритмов", С.А. Абрамов мне в этом помогут.
Спасибо за советы.

[Pavia]

Закон Адмала нарушаться не может. А вот неправильно его применить запроста.

По поводу оценки. Без глубокого знания архитектуры мы можем сделать оценку. А она может значительно отличаться от действительности в разы. К примеру КИХ филтер через умножение и сумирование и его аналог через БПФ. Первый имеет сложность O(N*M) второй O(N*log(N)). Но при этом хорошо оптимизировать второй трудно, а первый легко. Вот и выходит на практике что первый выгоднее по скорости чем второй. Так как работает в 5-50-200 раз быстрее.
5 оба максимально оптимизированы
50 не оптимизированы
200 оптимизирован только первый.

Так что без практике на железе трудно оценить.

[Zealint]

Pavia в сообщении #614964 писал(а):

Закон Адмала нарушаться не может. А вот неправильно его применить запроста.

Да, может быть и такое. Дело в том, что любой закон идеализирован, то есть не имеет прямого отношения к действительности. Например, в законе предполагается, что идеальное распараллеливание даёт уменьшение времени работы обратно пропорционально числу процессоров. Это допущение часто нарушается. Сам закон при этом действительно не нарушается, но кого это вообще интересует, если он не отражает действительности? Некоторые в таких случаях считают, что закон неадекватен по отношению к реальным процессам (нарушается его следствие). Фактически на практике получается так: закон не нарушается, а становится совершенно бесполезным, как и значительная часть прочей чисто теоретической чепухи.

[Cubic]

Pavia

Цитата:

По поводу оценки. Без глубокого знания архитектуры мы можем сделать оценку. А она может значительно отличаться от действительности в разы. К примеру КИХ филтер через умножение и сумирование и его аналог через БПФ. Первый имеет сложность O(N*M) второй O(N*log(N)). Но при этом хорошо оптимизировать второй трудно, а первый легко. Вот и выходит на практике что первый выгоднее по скорости чем второй. Так как работает в 5-50-200 раз быстрее.
5 оба максимально оптимизированы
50 не оптимизированы
200 оптимизирован только первый.

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

Цитата:

Так что без практике на железе трудно оценить.

Согласен, но я вот и хочу понят какие алгоритмы можно применить на практике, а какие нет. Больше даже интересует оценка o(), а не O().
У меня есть следующее соображение. Допустим я знаю, что Алгритму 3 требуется выполнить \mathbb{\theta}(n^2) умножений двух чисел за время T, а Алгоритму 1 \mathbb{\theta}(n^5) умножений, и у меня есть устройство (ПЛИС например) которое за время T может выполнить максимум (n^3) умножений. Следовательно Алгоритм 1 никак не получится использовать на данной ПЛИС.
Это без учета возможности параллельных вычислений. Их тоже нужно будет как-нибудь учесть...
А еще нужно будет учесть memory bandwidth, что тоже печально. Вообще работы мне хватит на месяц точно.