这个方法是BigO(n^2)还是BigO(nLog(n))？

Question

这是我编写的一个方法，用于检查两个字符串是否是彼此的预突变：

public static boolean permutation(String str1, String str2) {

boolean terminate = false;

for(int x = 0; x < str1.length(); x++){
    for(int y = 0; y < str2.length(); y++){
        if(y != str2.length() - 1){
            if(str1.charAt(x) == str2.charAt(y)){
                str1.replace(String.valueOf(str1.charAt(x)), "");
                str2.replace(String.valueOf(str2.charAt(y)), "");
                break;
            }
            
        }else{
            if(str1.charAt(x) != str2.charAt(y)){
                return false;
            }else{
                str1.replace(String.valueOf(str1.charAt(x)), "");
                str2.replace(String.valueOf(str2.charAt(y)), "");
            }
            
        }
        
    }
    
}

return true;

}

正如您在代码中看到的，我在另一个 for 循环中使用了一个 for 循环，但没有使用 y 检查 x 的所有元素（但有时使用 x 的当前值检查 y 的所有元素），所以我猜是 BigO(nLog(n))，因为我们没有整体比较所有元素，但我的想法告诉我这可能是 BigO(n^2)。此外，一旦满足某个条件，我就会删除索引，因此其他剩余的索引不会检查删除的元素，在我看来它是一个 BigO(nLog(n)) 但以防万一它不是我想知道为什么.

!UPDATE!: 由于缺乏知识，而且我在 7 分钟内完成了该算法，实际问题是 O(n^3)，我没有注意字符串的替换方法，它实际上是一个 O(n) 时间复杂度，也没有检查输入的长度是否相同，因此它 returned 为真，而在某些情况下它应该 return false，这是根据它判断的新代码结构我会说它是最好的 O(n) 和最坏的 O(n^2):

    public static boolean permutation(String str1, String str2){
    
    if(str1.length() != str2.length()){
        return false;
    }
    
    
    
    HashSet<Character> string1 = new HashSet<>();

    
    
    for(int x =0; x < str1.length(); x++){
        string1.add(str1.charAt(x));
    }
    
    for(int x = 0; x < str1.length(); x++){
        if(!string1.contains(str2.charAt(x))){
            return false;
        }
    }
    
    
    return true;
}

Answer 1

你没有考虑replace()方法的时间复杂度。需要O(N)的时间复杂度。

同意您根据特定条件处理字符串，但是 2 个 for 循环无论如何都会使时间复杂度为 O(N^2)。

因此，整体时间复杂度 = O(N^2 * N) = O(N^3)。

准确来说，如果str1的长度是N，str2的长度是M,那么时间复杂度~O(N * M * (N + M)).

这个方法是BigO(n^2)还是BigO(nLog(n))？

Is this method BigO(n^2) or BigO(nLog(n))?

algorithm

time-complexity