Самая длинная общая подпоследовательность
Рассмотрите 2 последовательности X [1.. m] и Y [1.. n]. memoization алгоритм вычислил бы LCS вовремя O (m*n). Там какой-либо лучший алгоритм должен узнать LCS wrt время? Я предполагаю, что memoization, сделанный по диагонали, может дать нам O (минута (m, n)) временная сложность.
8
задан tsudot 9 June 2010 в 05:53
поделиться
1 ответ
Если вы априори знаете верхнюю границу на максимальный размер k, который вас волнует, вы можете заставить алгоритм LCS выйти раньше, добавив дополнительную проверку во внутренний цикл. Это означает, что при k << min(m,n) вы можете получить малое время работы, несмотря на то, что вы выполняете LCS.
1
ответ дан 5 December 2019 в 18:57
поделиться
Другие вопросы по тегам: