Второй алгоритм (6) решения задачи о максимальной подпоследовательности
Листинг 8.3. Второй алгоритм (6) решения задачи о максимальной подпоследовательности
cumarr[-l] = О for i = [0. n)
cumarr[i] = cumarr[i-l] + x[i] maxsofar = 0 for i = [0, n) for j = [i . n)
sum = cumarr[j] - cumarr[i-l]
/* sum - сумма x[i . . j ] */ maxsofar = max(maxsofar. sum)
(В задаче 5 рассматривается проблема доступа к cumarr[-l].) Этот код требует 0(п2) операций; анализ проводится так же, как и для алгоритма 2а.
Рассмотренные три варианта алгоритмов исследуют все возможные пары начального и конечного индексов, вычисляя сумму элементов последовательности. Поскольку таких последовательностей 0(п ), ни один алгоритм, проверяющий их все, не может быть быстрее квадратичного. Можете ли вы придумать способ обойти проблему и получить более быстрый алгоритм?
Опубликовал vovan666
April 17 2013 00:00:30 ·
0 Комментариев ·
3924 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
