Что такое Big O этого самого длинного общего алгоритма

Question

Решение для этого: https://leetcode.com/problems/longest-common-subsequence/ Я понимаю, что могу использовать запоминание, но каково большое значение этой грубой силы al go? Я думаю, что его O (mnk), где m - длина текста1, а n - длина текста2, а k - самая длинная общая подпоследовательность. Правильный ли этот анализ?

public int longestCommonSubsequence(String text1, String text2, int index1, int index2) {
        int max1= 0;
        for(int i = index1; i < text1.length(); i++) {
            for(int j = index2; j < text2.length(); j++) {
                if(text1.charAt(i) == text2.charAt(j)) {
                    max1 = Math.max(1 + longestCommonSubsequence(text1, text2, i+1, j+1), max1);
                }
            }
        }
        return max1;
    }

Answer 1

Нет, ваш анализ определенно не верен. Время выполнения далеко не так низко, как O(mnk).

Поскольку функция рекурсивная и многие рекурсивные вызовы имеют одинаковые параметры, удобный метод анализа - подсчитывать время, проведенное не в рекурсивном режиме. вызовов, затем подсчитайте количество рекурсивных вызовов для каждого набора аргументов , а затем возьмите сумму по первому, умноженную на последний.

Более конкретно, пусть S(m, n, i, j) будет временем не тратится на рекурсивные вызовы, C(m, n, i, j) - это количество раз, которое функция вызывается с этими аргументами, и время выполнения общего алгоритма T(m, n). Тогда:

Рассмотрим только наихудший случай, когда каждый символ одинаков, так что условие if во внутреннем l oop всегда верно:

• Алгоритм имеет вложенный l oop, который повторяется (m - i) * (n - j) раз и выполняет Θ(1) работу (исключая рекурсивные вызовы) за итерацию, поэтому S ∈ Θ(mn) для большей части Термины в этой формуле.
• Гораздо хуже, C растет очень быстро . Грубо говоря, C является комбинаторной функцией, которая подсчитывает все различные последовательности пар, так что последовательность начинается с (0, 0) и заканчивается (i, j), а промежуточные члены монотонно растут в обоих компонентах.

Трудно сказать точно, насколько быстро C растет как функция i и j, но это определенно, по крайней мере, экспоненциально. Это можно увидеть, просто рассмотрев случай, когда i = j и члены последовательности похожи на (k, k); даже среди этих последовательностей число комбинаций равно 2^(i-1), поскольку последовательности этой формы соответствуют подмножествам {1, ..., i-1}.