Java 最长公共子串长度算法时间复杂度分析

Java 最长公共子串长度算法时间复杂度分析

算法代码:

public static int findMaxCommonSubstringLength(String str1, String str2) {
    int[] prevRow = new int[str2.length() + 1];
    int[] currentRow = new int[str2.length() + 1];
    int maxLength = 0;

    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                currentRow[j] = prevRow[j - 1] + 1;
                maxLength = Math.max(maxLength, currentRow[j]);
            }
        }
        // 更新prevRow数组为currentRow数组
        for (int j = 0; j <= str2.length(); j++) {
            prevRow[j] = currentRow[j];
        }
    }
    return maxLength;
}

时间复杂度分析:

该算法的时间复杂度为 O(n*m)，其中 n 为 str1 的长度，m 为 str2 的长度。

运行时间分析:

在该算法中，使用了两个长度为 str2.length()+1 的数组 prevRow 和 currentRow，因此在传入长度为 2000 的字符串时，需要分配的空间为 2001 个整数。每次循环中，需要比较两个字符是否相等，因此总共需要进行 n*m 次比较。

因此，当传入字符串长度都为 2000 时，最多需要花费的时间为 2001*2001=4,004,001 个比较操作，即最多需要花费 4,004,001 个单位时间运行。

总结:

该算法的时间复杂度为 O(n*m)，当输入字符串长度都为 2000 时，最多需要 4,004,001 个单位时间运行。