end

{m[1, n] – шукане значення}

Безпосередньо за алгоритмом неважко переконатися, що оцінкою його складності є O(n3).?

Підіб'ємо підсумок. В обох прикладах ми будували послідовності – шляхи на циліндрі або послідовності дужок. Характерним для них є те, що, кажучи неформально, коли зафіксовано якийсь компонент у їх середині, то оптимальний вибір компонентів у початку не впливає на оптимальний вибір у кінці, і навпаки. Саме ця незалежність позбавляє необхідності перебирати всі можливі послідовності і забезпечує складність наведених алгоритмів порядку O(mn) та O(n3) відповідно.

У задачі про три станки такої незалежності рішень на початку їх послідовності та в її кінці немає. Саме це змушує перебирати всі можливі послідовності та зумовлює незастосовність принципу оптимальності. Для цієї задачі немає алгоритмів, які б дозволяли будувати розв'язок із незалежних частин подібно до задачі про добуток матриць.

Існує величезний клас задач, розв'язки яких є послідовностями заданого вигляду, причому їх початок і кінець взаємозалежні. Для таких задач побудовано алгоритми складності не менше O(2n), де n – це величина, що характеризує розмір вхідних даних задачі. Але для них досі не побудовано алгоритмів, складність яких можна було б оцінити поліноміальною функцією від n. Поки що не доведено, що таких алгоритмів узагалі не можна побудувати, але саме до такої думки схиляються майже всі, хто мав справу з цими задачами.

Серед задач, розв'язок яких будується перебиранням варіантів, виділяються так звані NP-складні та NP-повні задачі. Обсяг і характер цієї книжки не дозволяють розпочинати знайомство з ними, тому зацікавлений читач може подивитися в книги [АХУ, РНД, ГД].