这种将 N 长度的消息修剪为 M 长度的解决方案的时间复杂度是多少？

Question

我正在尝试为以下问题获得正确的时间复杂度：

Input: a string contains spaces and words, and an integer M
Output: trim the string so the trimmed string length <= m and no cut-off word.
Sample:
S = "This is JavaScript", M = 10.
Expect: "This is" // because "This is Ja" is invalid, "JavaScript" is cut. 
S = "JavaScript", M = 5
Expect: "" // empty because the output "JavaS" is invalid.
S = "JavaScript", M = 10
Expect: "JavaScript"

这是我的代码：

function trimThis(S, M) {
    if (M > S.length) return S;
    let output = S.slice(); // Making a copy of the input is optional
    while (output.length > M) {
        const lastSpaceIdx = output.lastIndexOf(' ');
        if (lastSpaceIdx !== -1) {
            const endIdx = Math.min(lastSpaceIdx, output.length);
            output = output.slice(0, endIdx);
        }
        else return '';
    }
    // In JS we can also use trimEnd() to remove trailing spaces:
    while (output.length > 0 && output[output.length - 1] === ' ') {
        output = output.slice(0, -1);
    }
    return output;
}

我认为总时间复杂度为 O(N)，其中 n = len(S) 但由于 while 循环我不确定。

while 循环将运行 O(N - M) 次。在每次迭代中，代码执行 O(N) 操作来找到最后一个 space 索引，而 slice() 操作需要 O(N)，所以它看起来像 O(N^2)。然而，在每次迭代之后，字符串变得越来越小。

复制字符串的时间O(N)不会影响整体的大O。

Answer 1

时间复杂度是O(n²)，因为你重复执行一个slice，每次都会创建一个新的字符串。虽然slice的执行速度很快，但是时间不是常数，而是和长度成正比的。

您应该只使用索引，并在最后执行“昂贵的”slice。另请注意，不需要初始切片，因为字符串在任何方面都是不可变的。无法修改 S，即使您愿意。

这是您的代码，适用于最后只执行 slice。注意：我不会为变量名使用首字母大写，因为通常这是为构造函数的名称保留的。

function trimThis(s, m) {
    let endIdx = s.length;
    while (endIdx > m) {
        lastSpaceIdx = s.lastIndexOf(' ', endIdx - 1);
        if (lastSpaceIdx !== -1) {
            endIdx = lastSpaceIdx;
        } else return '';
    }
    while (endIdx > 0 && s[endIdx - 1] === ' ') {
        endIdx--;
    }
    return s.slice(0, endIdx);
}

let s = "We are living in interesting times";
let res = trimThis(s, 20);
console.log(res);

现在是 O(n)。

这种将 N 长度的消息修剪为 M 长度的解决方案的时间复杂度是多少？

What is the Time Complexity for this solution of trimming a message of N length at M length?

javascript

algorithm

big-o