这个java递归函数的时间复杂度是多少？

Question

class Solution {
    public static int countBinarySubstrings(String s) {
        int res = 0;
        for(int i = 0; i < s.length()-1; i++) {

            if(s.charAt(i) != s.charAt(i+1)) 
                res += countValid(s, i, i+1);
        }
        return res;
    }
    
    public static int countValid(String s, int start, int end) {
        //base case
        if(start < 0 || end >= s.length()) 
            return 0;
        if(end-start == 1)
            return countValid(s, start-1, end+1) + 1;
        if(s.charAt(start+1) == s.charAt(start) && s.charAt(end-1) == s.charAt(end))
            return countValid(s, start-1, end+1) + 1;
        else
            return 0;
    }
    
}

Leetcode问题https://leetcode.com/problems/count-binary-substrings/

该解决方案有效，但我很难提出递归解决方案的时间复杂度。

每当循环遇到s.charAt（i）！=s.charAt（i 1）时，它都会进行递归调用以展开，直到达到基本大小写或其他部分。

因为我遍历整个字符串，所以for循环是O（n）。但是如何确定将进行的递归调用的数量，因为它将取决于if条件。

至于空间复杂度，最坏的情况发生在s=“00…000011111…11”时。在本例中，01正好出现在中间，因此递归调用将继续扩展，直到开始索引和结束索引超出界限。到那时，代码将进行n/2次调用，因此空间复杂度为O（n）。

我被困在时间复杂度上。

Answer 1

首先，考虑任何给定的顶级调用isValid（）。

我们可以看到它调用自己的模式。它从可以假设为字符串中间的某个地方开始，并不断扩展边界，直到它们超出范围或数字不再匹配。在最坏的情况下（从中间开始并一直延伸到结尾，这导致调用方法n/2次，即时间复杂度类O（n）。

现在，我们可以考虑count tBinarySubstring（），它调用isValid（）n次。O（n*n）=O（n^2）。

就空间复杂度而言，在countBinarySubstrings（）中只分配了一个整数，在countValid（）中没有分配空间。在方法的空间复杂度中，我们通常不计算方法调用本身占用的堆栈空间，也不计算输入本身占用的空间，因此我们可以说这具有O（1）space complextiy（或O（n）如果要从递归调用中计算堆栈空间）。

请记住，O表示法记录过程的最坏情况复杂性。Ω表示法记录最佳情况，θ表示法记录平均情况复杂性，这通常有点难以计算，但我们通常不太关心它。