Большинство программистов реагируют на алгоритм 1 одинаково: «есть очевидный способ сделать его намного быстрее». Таких способов на самом деле два, причем конкретному программисту обычно очевиден лишь один из двух. Оба алгоритма обладают квадратичным временем работы — делают 0{пг) операций для массива размером п — и в обоих сумма x[i. .j] вычисляется за постоянное количество шагов, а не за j-1+l сложений как в алгоритме 1. Однако эти два алгоритма используют принципиально различные методы вычисления сумм за конечное число шагов.
Первый квадратичный алгоритм позволяет быстро вычислить сумму благодаря тому, что сумма x[i..j] легко получается из предыдущей: Использование этого свойства позволяет получить алгоритм 2а (листинг 8.2).
Листинг 8.2. Второй алгоритм (а) решения задачи о максимальной подпоследовательности
maxsofar = О for 1 = [0. п) sum = О
for i = [i. n) sum += x[j]
/* sum - сумма x[l .j] */ maxsofar = max(maxsofar. sum)
Операторы внутри внешнего цикла выполняются п раз, а те, что лежат внутри внутреннего, — не более чем п раз, так что время работы алгоритма составляет 0(п2).
Альтернативный квадратичный алгоритм вычисляет сумму во внутреннем цикле, обращаясь к структуре данных, которая строится отдельно, до начала первого цикла. Создается массив cumarr, i-й элемент которого содержит кумулятивную сумму значений x[0..i], поэтому сумму x[i..j] можно получить как разность cumarrfj] - cumarr[i-l]. В итоге получим алгоритм 26 (листинг 8.3).
Опубликовал vovan666
April 17 2013 00:00:28 ·
0 Комментариев ·
3357 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
