Презентация на тему: Место и значение алгоритмов в вычислительных задачах

Таблица 2

• Таблица 2

Хорошим критерием качества алгоритма является скорость роста его сложности в зависимости от увеличения размера входа. Рассмотрим пример, показывающий влияние порядка роста сложности алгоритма на увеличение максимально допустимого размера входных данных, которого можно достичь увеличением скорости ЭВМ, а также эффект применения более эффективного алгоритма (см. табл. 1 и 2). Из табл. 1 видно, что может обработать за 1 с входные данные размером 1000, в то время как -- входные данные не длиннее 9. Табл. 2 показывает, что для алгоритма десятикратное увеличение скорости ЭВМ позволяет увеличить размер входных данных, к которым его можно применять, только на три, тогда как для алгоритма размер входных данных можно по крайней мере утроить.

• Хорошим критерием качества алгоритма является скорость роста его сложности в зависимости от увеличения размера входа. Рассмотрим пример, показывающий влияние порядка роста сложности алгоритма на увеличение максимально допустимого размера входных данных, которого можно достичь увеличением скорости ЭВМ, а также эффект применения более эффективного алгоритма (см. табл. 1 и 2). Из табл. 1 видно, что может обработать за 1 с входные данные размером 1000, в то время как -- входные данные не длиннее 9. Табл. 2 показывает, что для алгоритма десятикратное увеличение скорости ЭВМ позволяет увеличить размер входных данных, к которым его можно применять, только на три, тогда как для алгоритма размер входных данных можно по крайней мере утроить.
• Следует, однако, иметь в виду, что порядок роста сложности алгоритма является определяющим только при обработке данных большого размера. Для задач с малым размером входных данных (а именно на таких данных и проверяется правильность студенческих алгоритмов) следует учитывать мультипликативные константы при сравнении алгоритмов. Например, предположим, что временные сложности алгоритмов и равны соответственно , , . Тогда будет наилучшим для данных размером -- для данных размером -- при , а -- только при В качестве примера приведем анализ временной сложности двух алгоритмов генерации перестановок из п. 4.11. Общую эффективность алгоритма генерации перестановок в лексикографическом порядке определяют две операции -- число транспозиций и число сравнений пар элементов в перестановке. Обозначим через и соответственно число транспозиций и число сравнений, выполняемых алгоритмом для порождения первых из перестановок. Поскольку для порождения каждой из подпоследовательностей перестановок с одним и тем же значением требуется транспозиций, а для каждого из переходов от одной подпоследовательности к другой требуется транспозиций, получаем следующее рекуррентное соотношение:
• утверждения: за счет увеличения временной сложности алгоритма можно понизить его емкостную сложность.
• Как правило, более эффективный алгоритм приводит к программе большего размера и требует больших усилий как на его разработку, так и на его обоснование