Какова сложность алгоритма?

Question

[richvoronov]

Затрудняюсь с оценкой сложности алгоритма

var isValid = function(s) {
    let res = s;
    while (res.indexOf('()') !== -1 || res.indexOf('[]') !== -1 || res.indexOf('{}') !== -1) {
      res = res.replace('()', '');
      res = res.replace('[]', '');
      res = res.replace('{}', '');
    }

    return !res;
};

Comments

[Олег Войтенко]

Вам по какой шкале?

У меня такая задачка была на собесе еще на джуна по JS. Это легкий алгоритм парсера строки с заменой подстрок.

[richvoronov]

спасибо,
ответил ниже другому автору вот так

глядя на `while(res.indexOf)` хочется сказать что O(n^2), но смущает меня `.replace`. Насколько я понимаю под капотом replace так же имеет цикл. Вот и хочу понять стоит ли его учитывать, либо я что-то не так понимаю

[res2001]

Операции indexOf можно вообще выкинуть, просто делайте replace в цикле. Причем сделайте 3 цикла (или вложенные циклы) и в каждом свой replace. Выполняйте replace в цикле до тех пор пока replace не вернет, что замен не было.
Не знаю как работает replace в JS, но можно replaceить не всю строку каждый раз, а с того места где закончился предыдущий replace. Или, если есть возможность делать replace всех вхождений, то надо его и использовать, тогда можно обойтись без циклов совсем.

Answer 1

[Alexandroppolus]

В лучшем случае O(N), в худшем O(N^2)

Если сделать по нормальному, всегда будет O(N)

Comments

[richvoronov]

спасибо

глядя на `while(res.indexOf)` хочется сказать что O(n^2), но смущает меня `.replace`. Насколько я понимаю под капотом replace так же имеет цикл. Вот и хочу понять стоит ли его учитывать, либо я что-то не так понимаю

[Alexandroppolus]

Конечно надо учитывать. Replace это O(N)

Answer 2

[Wataru]

Квадратичная сложность.

Решение со стеком будет линейным.

Answer 3

[Slava Rozhnev]

O = 3n^2

Answer 4

[mayton2019]

Я обычно оцениваю на глазок просто мысленно предполагая что данных очень много.
Например строка длиной 2 млрд символов.
В этом случае 3 линейных поиска по ней (indexOf) дадут нам формулу

O(n)

Это в негативном сценарии когда мы не нашли скобочек трех типов.

Но в позитивном сценарии если мы нашли - начинает работать еще более хардкорная логика
реплейсмента которая ... ну я не знаю как работает. replace(..) которая под капотом тоже имеет
свою complexity. Наверное тоже линейную если стоит билдер строк. Получается что линейная вложена
в другую линейную. Получается квадратичная.

o(n^2)

Вообще мне кажется что этот код не оптимален и его лучше просто переписать на какой-то replace
с регулярками чтоб заменять не только первое вхождение но и все. Впрочем я тут не сильно помню как
Js работает с заменой. Пускай знающие откомментируют.