时间戳

首页 > 解决方案 > 用迭代计算递归函数的时间复杂度

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

问题描述

我试图了解此代码的时间复杂度，该代码通过将字符串拆分为 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!的情况，对吧？

但是，如果我环顾四周（例如此处或此处），我会看到人们发布恒定的时间复杂度。我无法理解。有人可以帮我分解吗？

标签： javarecursionbacktracking

解决方案

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

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

111 111 111 111现在考虑一个长度的字符串12

  1. 有多少种方法可以组成第一个八位位组？=> 最小 1 ，最多 12 个字符中的 3 种方式。complexity:- O(3)

  2. 第二个八位组有多少种方法可以组成？=> 考虑到第一个八位字节使用 3 个字符，=> 最小 0 最大 9 个字符中的 3 种方式。complexity:- O(3)

  3. 第三个八位组有多少种方式可以组成？=> 考虑到第一个和第二个八位字节使用 6 个字符，从 6 个字符开始，最小 0 最大 3 种方式。complexity:- O(3)

  4. 你有多少种方法可以用剩余的字符组成第四个八位字节？=> 只有一种方法可以从剩余的 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。来自维基。

回溯是一种通用算法，用于寻找某些计算问题的解决方案，特别是约束满足问题，它逐步构建解决方案的候选者，并在确定候选者不可能完成到有效时立即放弃候选者（“回溯”）解决方案

PS:- 这个例子111 111 111 111是一个极端的例子，111.111.111.111这个字符串只能形成一个有效的 IP 地址。但是，循环/递归评估最多会发生 81 次。

推荐阅读