用迭代计算递归函数的时间复杂度

Question

我试图了解这段代码的时间复杂度，它通过将字符串分成 4 个部分来计算给定字符串的 IP 地址。每个部分由句点分隔，即 .

public List<String> restoreIpAddresses(String s, int parts) {

    List<String> result = new ArrayList<>();
    if (parts == 1) {
        if (isValidPart(s)) result.add(s);
        return result;
    }
    
    for (int i = 0; i < s.length(); i++) {
        String first = s.substring(0, i);
        if (!isValidPart(first)) {
            continue;
        }
        
        List<String> previous = restoreIpAddresses(s.substring(i, s.length()), parts - 1);
        
        for (String str: previous) {
            StringBuilder sb = new StringBuilder();
            result.add(first + "." + str);
        }
    }        
    
    return result;
    
}

private boolean isValidPart(String part) {
    if ( (part.length() > 1 && part.startsWith("0")) || 
         (part.length() > 3) || (part.length() == 0)
         (Integer.valueOf(part) > 255) ) return false;
      return true;
    }
}

由于for循环是O(n)，n是字符串的长度，在每次迭代中，for循环都对父for循环中传递的子字符串执行，所以O(n - 1) .所以按照这个逻辑，时间复杂度应该是n(n-1)(n-2) ....1，即最坏情况下的n!，对吧？

但是，如果我环顾四周（例如 here or here），我会看到人们发布了常数时间复杂度。我无法理解。谁能帮我分解一下？

Answer 1

考虑从上述算法生成 IP 地址，我们有两个约束。

有效 IP 为 0->255。这可以在恒定时间内进行评估。
将有 4 个八位字节。所以问题串应该分成4部分。

现在考虑长度为 12

的字符串 111 111 111 111

第一个八位组有多少种组合方式？ => 最少 1 种，最多 3 种方式，共 12 个字符。 complexity:- O(3)
第二个八位组有多少种组合方式？ => 最小 0 最多 9 个字符中的 3 种方式，考虑到第一个八位字节使用了 3 个字符。 complexity:- O(3)
第三个八位字节有多少种组合方式？ => 最小 0 最多 6 个字符的 3 种方式，考虑到第一个和第二个八位位组使用 6 个字符。 complexity:- O(3)
剩下的字符，你能用多少种方式组成第四个八位位组？ => 只有一种方法可以将剩余的 3 个字符组成一个八位位组。考虑到第一个、第二个和第三个八位位组使用 9 个字符。 O(1)

时间复杂度计算。

Time Complexity = product of complexities of each recursive function
                = O(3)*O(3)*O(3)*O(1)
                = 3*O(3) = O(1) = [constant-time] complexity

因此，无论您输入什么字符串，所有有效的 IP 地址都可以计算在 27 次迭代中。因此这个算法是常数时间O(1).

考虑到上面的理解，代码可以重写如下


public static List<String> restoreIpAddresses(String s, int position, int parts) {

        List<String> result = new ArrayList<>();
        // O(1) time complexity
        if (parts == 1) {
            if (position < s.length() && isValidPart(s.substring(position))) {
                result.add(s.substring(position));
            }
            return result;
        }

        // Iterate only thrice in each recursive function. O(3) time complexity
        for (int i = position; i <= position + 3; i++) {
            if (i > s.length()) {
                continue;
            }

            String first = s.substring(position, i);
            if (!isValidPart(first)) {
                continue;
            }

            List<String> previous = restoreIpAddresses(s, i , parts - 1);

            for (String str : previous) {
                StringBuilder sb = new StringBuilder();
                result.add(first + "." + str);
            }
        }

        return result;

    }

注意以上算法是经典backtracking problems的例子之一。来自维基。

Backtracking is a general algorithm for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution

PS:- 111 111 111 111 例子是一个极端的例子，只有一个有效的 IP 111.111.111.111 地址可以从这个字符串中形成。但是，loop/recursion 评估最多会发生 81 次。

用迭代计算递归函数的时间复杂度

Calculating Time Complexity of recursive function with iteration

java

recursion

backtracking