我对这个算法的时间复杂度分析是否正确？

Question

长话短说，我想验证我的以下代码的时间复杂度是否正确。

class Solution {
    public String reverseWords(String s) {
        int len = s.length(); int i=len-1, j=0;
        StringBuilder answer= new StringBuilder();
        while(i!=-1) {
            if(s.charAt(i)==' ') i--;
            else {
                j=i;
                while(j-1!=-1 && s.charAt(j-1)!=' ' ) j--; //j++;
                answer.append(s.substring(j, i+1)).append(' ');
                i=j-1;
            }
        }
        return answer.toString().trim(); //trim last index's space
    }
}

约束条件：

1 <= s.length <= 10^4
s包含英文字母（大小写）、数字和spaces ' '。
s

假设字符串长度为N。我的分析是进一步假设字符串 S 中有 K spaces 并假设其中有 L 个不同的 space 分隔单词，根据给定的约束我们可以得出结论 L>=1 和 K>= 0.

因此每个单词的平均长度为N-K/L，外循环因此运行K+L次，内循环独立于外循环运行2*(N-K)/L次使得总复杂度为2 (N-K)/L + K+L 这仍然是 O(N) 的顺序。

我是不是做出了错误的假设？有没有办法简化这个公式 2*(N-K)/L + K+L

Answer 1

我很确定运行时间是 O(n)。

虽然我不太确定你公式中的 N 是什么，但简化的一般规则是查看最大值。我假设 N 对你来说是最大的。 “+K+L”可以忽略不计，所以我们有 2*(N-K)/L。分配：(2/L)N - (2/L)K。我们删除常量并取最大的一个，所以它仍然是 O(n)

在我看来，查看运行时的一种更简单的方法是只查看您的代码在字符串中运行了多少次。你的第一个 while 一直持续到它触发 else。从您停止的索引开始，第二个循环一直计数直到停止。从那里，您将原来的 i 更改为 j 并继续进行。我认为代码会查看 i 两次停止的位置，但这不足以改变复杂性（解决方法是将 j 设置为 i - 1 因为你知道 i 处的字符已经不是 space 了） .

顺便说一句，N 通常表示输入的长度，无论是字符串长度还是数组大小。

我对这个算法的时间复杂度分析是否正确？

Am I right in my time complexity analysis for this algorithm?

java

performance

big-o

time-complexity