Первый алгоритм решения задачи о максимальной подпоследовательности
Листинг 8.1. Первый алгоритм решения задачи о максимальной подпоследовательности
maxsofar = О
for 1 = [0. п) for j = [1, п) sum = О
for k = [1. j] sum += х[к]
/* sum - сумма элементов x[i..j] */ maxsofar = max(maxsofar. sum)
Программа короткая, ясная, ее легко понять. К сожалению, она работает медленно. На моем компьютере ей требуется 22 минуты, если п=10 ООО, и 15 дней, если п=100 ООО. Вопросы, связанные с временем выполнения, будут детально рассмотрены далее в разделе 8.5.
Конкретные данные о времени работы программы хорошо приводить в байках, но почувствовать реальную эффективность алгоритма можно, используя оценку эффективности с помощью понятия «О-большое», описанного в разделе 6.1. Внешний цикл выполняется ровно п раз, средний — не более п раз на каждый из проходов внешнего цикла. Перемножив эти величины, получим, что код внутри среднего цикла выполняется 0(п2) раз. Внутренний цикл выполняется не более п раз, поэтому его мы тоже записываем как 0(п). Перемножив все эти величины, получим, что время работы алгоритма пропорционально я3. Такие алгоритмы называются кубическими.
Опубликовал vovan666
April 17 2013 00:00:24 ·
0 Комментариев ·
3414 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
