Третий алгоритм решения задачи о максимальной подпоследовательности
Листинг 8.4. Третий алгоритм решения задачи о максимальной подпоследовательности
И oat maxsum3(1, u)
if (1 > u) /* пустой массив */ return О if (1 == u) /* один элемент */ ret urn ma x(0, x[1]) m = (1 + u) / 2
/* m поиск максим поел, слева от границы */ lmaxc = sum = О for (i = т; i >= 1; i- -) sum += x[i]
1 max = max(1 max, sum)
/* m- поиск максим поел справа от границы */ rma хс = sum — О for i = (m. и]
sum += х[i] rmax - max(rmax. sum) return maxdmax+rmax, maxsum3(l , m), maxsum3(m+l. u))
Алгоритм 3 запускается вызовом
answer = maxsum3(0, n-1)
Код достаточно сложен, в нем легко ошибиться, но он решает задачу за 0(п log п) операций. Мы можем доказать это несколькими способами. Неформальное доказательство заключается в том, что алгоритм выполняет работу 0(я) на каждом из 0(log п) уровней рекурсии. Доказательство можно сделать более строгим, используя рекуррентные соотношения. Если Т(п) обозначает время решения задачи размера п, то 7X1) = 0(1) и Т(п) = 2Т(п /2) + О(п). В задаче 15 показано, что решение этого рекуррентного соотношения: Г(п) = 0(nlogn).
Опубликовал vovan666
April 17 2013 00:00:34 ·
0 Комментариев ·
3644 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
