Временная сложность подпоследовательности max char

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

Мы можем использовать нотацию Big O, чтобы вычислить ее сложность здесь

Если мы посмотрим на код, мы должны использовать основные циклы - for и while

Цикл for будет выполнять n итераций.

Между тем цикл while будет выполнять n (n + 1) / 2 итерации - которые представляют сумму ряда из n чисел.Его сложность определяется выражением O (n ^ 2);

Поэтому сложность кода, если n * n ^ 2 = O (n ^ 3)