Блог пользователя vsb

Завали перебор (задача C с TCM/SE #1)
Автор vsb, 14 лет назад, По-русски
Всем привет!

Мне рассказали решение за O(n^2) с использованием КМП, я написал для начала решение, но вместо умного КМП использовал обычный string::find, и общая сложность всего решения должна была быть чуть ли ни O(n^4). 
Послал и получил ОК...
Ощущения какой-то мистики, кто сможет "зачеленжить" мое решение или объяснить, какая его истинная ассимптотика?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ну, верхние два цикла (по i и по len) аммортизируются, давая O(n). Так что если реализация find хоть немного интеллектуальна, то алгоритм за O(n^2)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо за ответ, но кажется что find работает за O(n * m). Но очевидна одна вещь: find будет вызываться не более чем 2n Раз. И если бы find работал за линию, то да, понятно почему общая сложность O(n^2). Но это не так. Может можно как-то строго показать, что суммарное количество сравнений в find будет O(n^2)?..

    Забавно, самая сложная из решенных задач решается таким простым подходом :)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ну, заставить find работать O(n * m) постоянно тут очень сложно прямо скажем
      → Ответить