最大字符子序列的时间复杂度

Question

此函数返回最大字符子集序列。示例输入和输出如下所示。有人可以帮助解决时间复杂性问题吗？

function shortenString(str) {
    let result = str.charAt(0);
    for (let i = 1; i< str.length; i++) {
        const c = str.charAt(i);
        let j = i - 1;

        while (j >= 0) {
            const charA = result.charAt(j);
            const charB = str.charAt(i);

            console.log(`comparing ${charA} to ${charB}`);

            if (result.charAt(j) < str.charAt(i)) {
                result = result.substring(0, j);
            }
            j--;
        }
        result = result + str.charAt(i);
    }

    return result;
}

Answer 1

我们可以使用大O符号来计算其复杂性here

如果我们看一下代码，我们必须主循环- for和while

for循环将进行n次迭代。

同时，while循环将执行n(n+1)次/2迭代-这表示一系列n个数字的总和。其复杂度为O(n^2)；

因此，当n*n^2 = O(n^3)时，码的复杂度