Java简单应用程序复杂性

Question

我必须解决面试中的一个问题，但我不明白一些事情。问题是，对于像“我们喜欢远足”这样的字符串，要反转字符串，如下所示:“ew ekil gnikih”，这意味着将字符串分解为:str.split(“”)，然后每个单词反转并添加到新字符串。

问题出现在问题的最后，因为我们在问一些关于复杂性的问题，例如:“- 预计最坏情况时间复杂度为 O(N)” - 预期最坏情况的空间复杂度为 O(N)(不计算输入参数所需的存储)

我这样解决了这个问题:

public static String solution(String S){

    if(S.length()>1 && S.length()<200000){

        String toReturn = "";

        String[] splitted = null;
        if(S.contains(" ")){
            splitted = S.split(" ");
        }
        else{
            splitted = new String[]{S};
        }

        for(int i=0;i<=splitted.length-1;i++){
            String wordToChange = splitted[i];
            String reversedWord = "";
            for(int j=wordToChange.length()-1;j>=0;j--)
                reversedWord+=wordToChange.charAt(j);

            toReturn+=" " + reversedWord;

        }

        return toReturn.trim();

    }
    return null;
}

对于复杂性请求我应该做什么？谢谢!

Answer 1

关于时间复杂度:

最坏情况 O(N) 意味着您应该遇到最坏情况，其中您计算 N 次迭代以获得结果，在您的情况下，您将字符串拆分为字符串数组 [操作可能需要 O (N)，但它取决于方法 split()]，然后对于数组中的每个字符串，您从字符串的末尾开始并反转字符。所以最坏的情况是 O(N) + O(N)... = O(N)

关于空间复杂度:

每个字符串都是一个对象，您为创建的每个字符串在内存中保留空间，这里您有一个字符串数组，意味着您为从原始字符串中拆分的每个单词或字母创建一个对象。最坏的情况是像“I am theone”这样的字符串，其中为每个字符创建一个字符串 -> O(N)

希望这能解答您的疑问