@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;
};
  • Вопрос задан
  • 236 просмотров
Решения вопроса 1
Alexandroppolus
@Alexandroppolus
кодир
В лучшем случае O(N), в худшем O(N^2)

Если сделать по нормальному, всегда будет O(N)
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Квадратичная сложность.

Решение со стеком будет линейным.
Ответ написан
Комментировать
rozhnev
@rozhnev
Fullstack programmer, DBA, медленно, дорого
O = 3n^2
Ответ написан
Комментировать
@mayton2019
Bigdata Engineer
Я обычно оцениваю на глазок просто мысленно предполагая что данных очень много.
Например строка длиной 2 млрд символов.
В этом случае 3 линейных поиска по ней (indexOf) дадут нам формулу

O(n)

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

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

o(n^2)

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы