Изменения

Отождествим все профили с один переходом с теми, кто их них получается. Это будет выглядеть так: пусть pr2 <tex>pr_2</tex> (и только он) получается из pr1<tex>pr_1</tex>, который, в свою очередь, получается из pr0<tex>pr_0</tex>. Тогда имеются такие соотношения: <tex>d[pr0pr_0, pr1pr_1]=1</tex>, <tex>d[pr1pr_1, pr2pr_2]=1</tex>. Отождествить pr1 <tex>pr_1</tex> и pr2 <tex>pr_2</tex> {{-- -}} это, по сути, заменить эти два соотношение на одно, то есть теперь <tex>d[pr0pr_0, pr1pr_1]=0 </tex> и <tex>d[pr1pr_1, pr2pr_2]=0</tex>, но <tex>d[pr0pr_0, pr2pr_2]=1</tex>, и так далее.

В итоге получаем асимптотику 2nn <tex>2^nn</tex> (количество переходов, то есть время на вычисление <tex>a[i]</tex>) умножить на <tex>m </tex> равно <tex>O(2nnm2^nnm)</tex>. Она значительно лучше всего, что мы получали до сих пор, и это серьезный повод использовать изломанный профиль вместо обычного.