Книга Жемчужены творчества программистов на IT БАЗАР

		\

Книга Жемчужены творчества программистов на IT БАЗАР


Различие в постоянных множителях, составляющее 6.5 млн, позволяет кубическому алгоритму стартовать с лучшим временем, но линейный алгоритм обязан вырваться вперед. Переломный момент наступает при N = 2400, где каждый из этих алгоритмов затрачивает около 50 с:

Век

го 5 I S et

Рис. 7.6	Секунда — Миллисекунда -Микросекунда Наносекунда ю"Ч Сгэу-1	I з- Ю О
Рис. 7.6		о ю аз О. ОС а m

----------₍--------------_[-------------!-------------_\|-------------j--------- 10° 10' 10² 10³ 10⁴ 10⁵ 10^йРазмерность задачи (N)

7.6. ОСНОВНЫЕ ПРИНЦИПЫ История этой задачи проливает свет на методы разработки алгоритмов. Задача возникла в процедуре сопоставления с эталоном, разработанной У. Гренандером из Университета Брауна, и описана для двумерного случая в задаче 7, где подмассив с максимальной суммой являлся оценкой с максимальной вероятностью некоторого эталонного изображения, представленного в виде цифр. Так как для решения двумерной задачи потребовалось слишком много времени, Гренандер свел ее к одномерной, чтобы лучше понять ее структуру. 97

Страница №110