748
правок
Изменения
→Время работы
==Время работы==
Для определения времени работы алгоритма надо заметить, что <tex>i,k=0,\ldots n</tex>, <tex>k_j=0,\ldots m</tex> где <tex>j=1,\ldots m</tex>. Из рекуррентной формулы очевидно, что подсчет одного значение <tex>f_i(k,k_1, \ldots ,k_m)</tex> нужно <tex>O(m)</tex> времени. Значит алгоритм работает за <tex>O(n^2m^{m+1})</tex> или <tex>O(n^2)</tex> для фиксированного <tex>m</tex>.
==См. также==
