Java 简单的应用程序复杂性

Question

我为了面试解决了一个问题，有什么没看懂。问题是，对于像 "we like hiking" 这样的字符串，要像这样反转字符串："ew ekil gnikih"，这意味着，要像这样分解字符串：str.split(" ") 然后，每个词到反转并添加到新字符串。

问题在问题的最后，因为在问一些关于 Complexity 的问题，比如： “ - 预期的最坏情况时间复杂度为 O(N)” - 预期的最坏情况 space 复杂度为 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)

大约 space 复杂度：

每个字符串都是一个对象，你在内存中为你创建的每个字符串保留 space，这里你有一个字符串数组，意味着你为从原始拆分出来的每个单词或字母创建一个对象细绳。最坏的情况是像 "I a m t h e o n e" 这样的字符串，您在其中为每个字符创建一个字符串 -> O(N)

希望这能澄清你的疑惑

Answer 2

我认为至少在时间复杂度上这不是正确答案。

在我看来，字符串的拆分很可能是 O(n) 的复杂度。它只会增加下一个复杂性，因此我们可以忘记它。

现在您要创建一个空字符串并在每个字符串顶部连接一个字符。在这里，您假设此操作与将值插入数组一样便宜 (O(1))。

在这种情况下，您应该假设，您每次都在使用成员方法 concat() 创建一个新的字符串。如果您有机会查看 String.concat(String) 的实现，您会发现此方法正在创建另一个长度为 string1.length + string2.length 的 char[] 和正在将 string1 和 string2 复制到其中。所以单独这个方法的复杂度为O(n).

因为您要将 n 个字符连接到一个长度为 n 的单词，所以它的复杂度为 O(n * (n / 2)) = O(n^2) 一个单词。假设只有一个单词的最坏情况，您的复杂度为 O(n^2).

class

我同意您的代码的 space 复杂度 class O(n)。但这只是在 JVM 的智能重用你未使用的假设下 space.

你的代码应该可以工作，但我认为它不是解决这个问题的好代码。您可以使用 StringBuilder 或直接对 char[].

进行操作来改进它

StringBuilder 是个好主意，因为它的行为类似于 Vector 或 ArrayList。我在其后台工作的 char[] 比 String 大得多。如果超出容量（通过使用 append() 方法），它将创建一个更大的数组，大约是前一个后备数组大小的 2 倍。这可能只是 O(nlogn) 的时间复杂度。但是您可以通过使用与初始 String 相同大小的容量初始化 StringBuilder 来进一步调整它。这意味着支持 char[] 根本不会被复制，因为你不会超过它的容量。

这是一个使用 char[] 的例子：

private static void reverseCharArray(char[] result, int start, int end) {
    int halfDifference = (end - start) / 2;
    for (int i = 0; i < halfDifference; i++) {
        char buffer = result[start + i];
        result[start + i] = result[end - i - 1];
        result[end - i - 1] = buffer;
    }
}    

public static String reverseWordInString(String string) {
    char[] stringAsCharArray = string.toCharArray();

    int indexStart = 0;
    for (int indexEnd = 0; indexEnd < stringAsCharArray.length; indexEnd++) {
        if (stringAsCharArray[indexEnd] != ' ') {
            continue;
        }
        StringOperations.reverseCharArray(stringAsCharArray, indexStart, indexEnd);
        indexStart = indexEnd + 1;
    }
    StringOperations.reverseCharArray(stringAsCharArray, indexStart, stringAsCharArray.length);

    return String.valueOf(stringAsCharArray);
}

Java 简单的应用程序复杂性

Java simple application Complexity

java

time-complexity

space-complexity