java - 该算法的时间复杂度: is it O(n^2) or O(n)

Question

我正在尝试解决 Leetcode 的“Reverse Words in a String III”。我想出了一个解决方案，但我认为我的时间复杂度是 O(n^2)。我的代码能够通过所有测试用例。我的代码如下:

class Solution {
    public String reverseWords(String s) {
        if(s.isEmpty())
            return "";

        StringBuilder result = new StringBuilder();        
        String[] str = s.split("\\s+");
        for(String s1:str){
            char[] c1  = reverseChar(s1);
            result.append(c1).append(" ");
            }
        return result.toString().trim();
    }

    public char[] reverseChar(String s){
        char[] c = s.toCharArray();
        int i = 0;
        int j = c.length-1;

        while(i<j){
                char temp = c[i];
                c[i] = c[j];
                c[j] = temp;
                j--;
                i++;
            }
        return c;
    }

}

Answer 1

O(n) ...实际上，当字符串长度较短时，由于 JVM 的启动/拆卸成本，O(n) 会稍微少一些。

如果您有兴趣准确了解，我建议您研究 Java Micro-benchmarking Harness (JMH)(回复: https://www.oracle.com/technetwork/articles/java/architect-benchmarking-2266277.html )。

我不推荐以下穷人基准；然而，它仍然回答了这个问题。

    public static void main (String[] args) {
        Random r = new Random();
        char[] chars = new char[100_000]; // change this value to other benchmarks
                for (char c : chars) {
            c = (char) (r.nextInt(90) + 32);
        }

        Solution s = new Solution();
        long x1  = System.currentTimeMillis();
        s.reverseWords(Arrays.toString(chars));
        long x2 = System.currentTimeMillis();

        System.out.println("duration = " + (x2 - x1));
    }