Время - выполнение - алгоритм
Cтраница 4
 |
Построение опорных прямых эквивалентно поиску пересечения в двойственном пространстве. [46] |
Ключевым моментом этого метода является эффективный способ построения соединения. Опираясь на то, что соединение можно определить в результате решения задачи линейного программирования, авторы алгоритма воспользовались методом решения задач линейного программирования за линейное время, который был недавно предложен Меджиддо и Дайером и подробно будет рассмотрен в разд. Обозначим через hi и h2 ( hi - f - h2 h) число вершин оболочки соответственно слева и справа от соединения, а через T ( N, h) время выполнения алгоритма. [47]
Анализ низкой производительности с использованием О-нотации освобождает аналитика от необходимости включать в рассмотрение характеристики определенной машины. Выражение время выполнения алгоритма равно O ( f ( N)) не зависит от входных данных и полезно для распределения алгоритмов по категориям в независимости от входных данных и деталей реализации, и таким образом отделяет анализ алгоритма от какой-либо определенной его реализации. В анализе мы, как правило, отбрасываем постоянные множители. В большинстве случаев, если мы хотим знать, чему пропорционально время выполнения алгоритма, - N или logAf, - не имеет значения, где будет выполняться алгоритм - на небольшом компьютере или на суперкомпьютере; более того, не имеет значения даже то, хорошо или плохо реализован внутренний цикл алгоритма. [48]
Однако при анализе низкой производительности существуют и некоторые трудности. Для определенных алгоритмов может существовать весомая разница между временем, необходимым для решения задачи в случае худших входных данных, и временем, необходимым в случае данных, которые встречаются на практике. Например, быстрое объединение в случае низкой производительности требует времени выполнения, пропорционального N, и пропорционального лишь logW для обычных данных. Часто не удается доказать, что существуют входные данные, для которых время выполнения алгоритма достигает определенного предельного значения; можно лишь доказать, что время выполнения будет ниже этого предела. [49]
 |
Информационные потоки в микропроцессорной системе. [50] |
Но при этом надо учитывать, что все свои операции процессор выполняет последовательно, то есть одну за другой, по очереди. Конечно, существуют процессоры с параллельным выполнением некоторых операций, встречаются также микропроцессорные системы, в которых несколько процессоров работают над одной задачей параллельно, но это редкие исключения. С одной стороны, последовательное выполнение операций - несомненное достоинство, так как позволяет с помощью всего одного процессора выполнять любые, самые сложные алгоритмы обработки информации. Но, с другой стороны, последовательное выполнение операций приводит к тому, что время выполнения алгоритма зависит от его сложности. Простые алгоритмы выполняются быстрее сложных. В традиционной цифровой системе можно легко организовать параллельную обработку всех потоков информации, правда, ценой усложнения схемы. [51]
Временная и емкостная сложности. Время и объем памяти, используемые алгоритмом, являются двумя главными мерами эффективности конкретного алгоритма. Обычно мы подсчитываем лишь число ключевых операций, например сравнений, выполняемых алгоритмом, и представляем его в виде функции от размера входных данных. Поступая таким образом, мы должны гарантировать, чтобы число неучитываемых при подсчете операций было пропорционально числу ключевых операций, так что время выполнения алгоритма отличалось бы от полученной при таком подсчете оценки лишь постоянным множителем. Что касается объема памяти, требуемого при выполнении алгоритма, то мы подсчитываем максимальный объем памяти, который может потребоваться в какой-либо момент выполнения алгоритма. Эта величина также представляется в виде функции от размера входных данных. [52]
Как известно, все, что нужно для суммирования, - это простой итерационный цикл, но тут возникает одна проблема. Точность вычислений на ЭВМ ограничена, а весь смысл этого упражнения в том, чтобы найти много-много цифр числа я, значительно превзойдя обычную точность. Первое, что приходит в голову, - промоделировать ручные методы выполнения арифметических действий. Будем представлять числа очень большими целочисленными массивами ( по одной десятичной цифре в каждом элементе), тогда ясно, как составить программы сложения, вычитания и умножения. Запрограммировать ручной метод деления несколько сложнее, но все же возможно. Неприемлемым, однако, оказывается время выполнения алгоритмов. Если речь идет об операциях над числами из тысяч цифр, то такие расходы будут нам не по карману. К счастью, имеются лучшие алгоритмы. [53]
Достоинства динамического принципа являются недостатками статического и наоборот. Таким образом, если не удается в чистом виде использовать для реализации алгоритма управления расчетами статический принцип, то приходится использовать как статический, так и динамический принципы. Для того чтобы смягчить недостатки и усилить достоинства каждого из них, целесообразен следующий подход. Модули, реализующие основные функции математической модели, строить как автономные. Это позволяет использовать для управления расчетами при выполнении основных функций статический принцип. Так как эти модули, как правило, отражают особенности конкретной математической модели, то их относительно невысокий уровень стандартизации не будет существенно влиять на организацию разработки специального математического обеспечения в целом. На алгоритм управления расчетами возлагается часть функций по регулированию времени выполнения алгоритмов математической модели. [54]
Страницы: 1 2 3 4