计算递归算法的最坏情况运行时复杂度

Question

在课堂上，我已经开始学习如何计算各种算法的运行时复杂度函数，并发现这很困难。我试图在下面计算递归算法的最坏情况下的运行时复杂性。

目前，我选择我的基本操作是对两个字符的索引进行比较，这发生在if语句中。然而，这个if语句是嵌套的，我不确定这对递归算法中的t（n）有何影响。

我认为最坏情况下的运行时复杂性是t(n) = N(N-1) = N^2 -1 or just O(n)=N^2?，这是正确的吗？我认为在最坏的情况下，每个n个字符都会在外部if语句中进行检查，这意味着n-1个字符会在内部if语句中被比较。

public class StringShuffleTest {
    public static boolean isOrderedShuffle(String a, String b, String c){
        //variables for the size of Strings a, b and c.
        int n = a.length();
        int m = b.length();
        int len = c.length();     
        //if the length of c is not the length of a + b, return false.
        if (len != (n + m)){
            return false;
        }
        //if String c contains String b as a substring, then remove String b from c and make m = 0.
        //This statement avoids errors when dealing with Strings with very similar characters.
        if (c.contains(b)){
            c = c.replace(b, "");
            m = 0;
        }
        //if the length of a or b is 0, and c equals a or b, return true, otherwise,
        //return false.
        if (n == 0 || m == 0){
            if (c.equals(a) || c.equals(b)){
                return true;
            }
            else
                return false;
        }
        //if String a has length 1, remove a from String c and make String a empty.
        if (n == 1){
                c = c.substring(0, c.indexOf(a.charAt(0))) + c.substring(c.indexOf(a.charAt(0)) +1);
                a = "";
                return isOrderedShuffle(a, b, c);
            }
        //An ordered shuffle of two given strings, a and b, is a string that can be formed by interspersing
        //the characters of a and b in a way that maintains the left-to-right order of the characters from each
        //string.
        //Recursive algorithm to determine if String c is an ordered shuffle of a and b.
        else
        if (c.indexOf(a.charAt(0)) >= 0){
            int indexOfFirsta = c.indexOf(a.charAt(0));
            int indexOfSeconda = c.indexOf(a.charAt(1));
            if (indexOfFirsta <= indexOfSeconda){
            c = c.substring(0, indexOfFirsta) + c.substring(indexOfFirsta +1);
            a = a.substring(1, n);
                System.out.println(a);
                System.out.println(c);                   
            return isOrderedShuffle(a, b, c);
            }
        else
            if (c.indexOf(b.charAt(0)) >= 0){
                    int indexOfFirstb = c.indexOf(b.charAt(0));
                    int indexOfSecondb = c.indexOf(b.charAt(1));
                    if (indexOfFirstb <= indexOfSecondb){
                        c = c.substring(0, indexOfFirstb) + c.substring(indexOfFirstb +1);
                        b = b.substring(1, m);
                        System.out.println(b);
                        System.out.println(c);
                    return isOrderedShuffle(a, b, c);
                }
        }
        }
    return false;         
    }       
public static void main(String[] args) {
    System.out.println(StringShuffleTest.isOrderedShuffle("abc", "def", "abedcf")); 
}
}

Answer 1

如果将时间复杂性分析分解为多个部分，则会有所帮助。

我们知道，对于isOrderedShuffle的每个调用，我们至少删除一个字符。现在，让我们假设每次呼叫isOrderedShuffle的复杂性是C.

T（n）=T（n-1）+C

现在我们需要弄清楚C是什么。要做到这一点，你需要弄清楚函数中最复杂的运算是什么。在这种情况下，我们可以查看String的indexOf函数。当使用一个字符作为参数调用indexOf时，时间复杂度为O（n），其中n是我们正在搜索的字符串的长度（如果感兴趣，请参阅此答案）。在你的算法中，字符串是c。所以，我们假设长度是n。indexOf被称为常数。

C=O（n）

因此，

T（n）=T（n-1）+n

我让你把它归结为一个封闭的形式。