如何计算嵌套在 for 循环中的 while 循环的时间复杂度？

Question

所以我这里有这段代码，我只是想了解时间和 space 复杂性。

对于时间复杂度，我认为它是 O(n^2) 因为它在 while 循环中最多经历 n - 1 次循环并且它将在 for 循环中经历 n 次所以它将是 O(n (n-1)) 这是 O(n^2) 和 space 复杂度我认为它是 O(n) 因为它是线性的 space.

我不知道我说的对不对，如果我错了，有人可以纠正我的想法吗？提前致谢。

    // Write your code here
    let visited = new Array(s.length).fill(false);
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        let j = i + 1;
        visited[i] = true;
        while (j < s.length && s[j] === s[i] && !visited[j]) {
            visited[j] = true;
            count++;
            j++;
        }
    }
    return count;

Answer 1

这是 O(n) 的时间复杂度，因为：

while (j < s.length && s[j] === s[i] && !visited[j]) {

要满足此条件，visited[j] 必须为假，当它满足时，您就可以

visited[j] = true;

因此，上面的行只能运行与 visited 数组中的项目一样多。如果 while 循环运行结束 第一次 外部迭代（当 i 为 0 时），那么它永远不会运行在任何其他外部迭代中。如果 while 在第一次迭代 visited 的中途循环运行，在第二次迭代的另一半中，它永远不会运行用于其余的外部迭代.所以，这部分代码：

    while (j < s.length && s[j] === s[i] && !visited[j]) {
        visited[j] = true;
        count++;
        j++;
    }

永远不会运行超过总数的 visited.length 次。

外层循环当然是O(n)。所以，你得到

outer loop: O(n)
+ inner loop: O(n) when summed over all iterations of the outer loop
= O(n)

如何计算嵌套在 for 循环中的 while 循环的时间复杂度？

How to figure out time complexity for a while loop nested in a for loop?

javascript

time-complexity

big-o

space-complexity