Спасибо большое, смотрю видеоуроки на перёд по своему предмету в ВУЗе. Очень доходчиво объясняете материал. Жаль, что видео такое короткое, я бы ещё послушал.)
9:34 Не получилось понять этот момент. Как тогда быть, ключа do в этом дереве уже не может существовать, потому что имеющаяся "o" - false? Или нам нужно добавить еще одну "o" рядом и сделать ее is_key true?
Где-то я уже видел этот видос. :D Но меня мучает вопрос: почему О(|key|)? Если я правильно понял, то |key| - это модуль ключа, т.е. длина(видимо, по аналогии с векторами). То есть, это тот же О(n), где n - длина ключа? Если это так, то у меня вопрос: а почему это тут такая сложность? Ведь нигде нет ограничений на то, каким должно быть дерево и сколько у каждого узла может быть детей. Это значит, что у нас может быть дерево, где будет корень с M детей(все 1-буквенные). И предположим, что у дерева будет строго 1 уровень в глубину. Но ведь в таком случае получится, что для для нахождения ключа нам придется перебрать М вариантов в худшем случае. И тогда сложно будет не О(|key|), а О(М). И, кажись, это будет справедливо для каждого уровня: на каждый символ в ключе нам придется перебирать все ключи на текущем уровне дерева. Разве нет?
Все верно расписали! Взял из теории по префиксному дереву. Вероятно, там полагают длину ключа переменной, а множества проверок - некоторой постоянной опреацией, в итоге она выносится на O большое и остается только длина ключа. Но этом мои догадки. Главное, конечно, понимать как происходит поиск в деталях.
@@selfedu_rus, кстати, да, это хорошее замечание про константу. Там реально все будет сводиться О(n), т.к. мы предполагаем, что дерево уже сформировано и не будет меняться от ключа к ключу. Об этом я как-то не задумался. Но, в любом случае, такая структура данных, на первый взгляд, может оказаться крайне неэффективной - как раз-таки из-за этих констант.
@@7IdE часто она применяется для слов, и максимум число потомков - размер алфавита языка, т.е. не очень много, ну и выбрать всех потомков по префиксам - это тоже классная фишка этого дерева )
@@selfedu_rus, хммммм. И в условном английский словаре в худшем случае будет О(26 * |key|). Коэф, конечно, коэф большой, но не настолько, чтобы это все медленно работало. В целом, спасибо за ответы.
То есть нам нужно ещё хранить структуру для хранение веток дерева Так как я понял здесь нет только левого и правого потомка К тому же могут быть ключи с похожи значениями 'ror', 'or' и их уже запишем в разных ветвях. В чём же преимущество?
За доту и доку респект
Зашёл в комменты только ради этого)
Спасибо большое, смотрю видеоуроки на перёд по своему предмету в ВУЗе. Очень доходчиво объясняете материал. Жаль, что видео такое короткое, я бы ещё послушал.)
Я в шоке от количества дельных роликов на этом канале Сергея.
Отличное видео! Спасибо Вам за эти занятия!
9:34 Не получилось понять этот момент. Как тогда быть, ключа do в этом дереве уже не может существовать, потому что имеющаяся "o" - false? Или нам нужно добавить еще одну "o" рядом и сделать ее is_key true?
Где-то я уже видел этот видос. :D
Но меня мучает вопрос: почему О(|key|)? Если я правильно понял, то |key| - это модуль ключа, т.е. длина(видимо, по аналогии с векторами).
То есть, это тот же О(n), где n - длина ключа?
Если это так, то у меня вопрос: а почему это тут такая сложность?
Ведь нигде нет ограничений на то, каким должно быть дерево и сколько у каждого узла может быть детей.
Это значит, что у нас может быть дерево, где будет корень с M детей(все 1-буквенные). И предположим, что у дерева будет строго 1 уровень в глубину.
Но ведь в таком случае получится, что для для нахождения ключа нам придется перебрать М вариантов в худшем случае. И тогда сложно будет не О(|key|), а О(М).
И, кажись, это будет справедливо для каждого уровня: на каждый символ в ключе нам придется перебирать все ключи на текущем уровне дерева.
Разве нет?
Все верно расписали! Взял из теории по префиксному дереву. Вероятно, там полагают длину ключа переменной, а множества проверок - некоторой постоянной опреацией, в итоге она выносится на O большое и остается только длина ключа. Но этом мои догадки. Главное, конечно, понимать как происходит поиск в деталях.
@@selfedu_rus, кстати, да, это хорошее замечание про константу.
Там реально все будет сводиться О(n), т.к. мы предполагаем, что дерево уже сформировано и не будет меняться от ключа к ключу.
Об этом я как-то не задумался.
Но, в любом случае, такая структура данных, на первый взгляд, может оказаться крайне неэффективной - как раз-таки из-за этих констант.
@@7IdE часто она применяется для слов, и максимум число потомков - размер алфавита языка, т.е. не очень много, ну и выбрать всех потомков по префиксам - это тоже классная фишка этого дерева )
@@selfedu_rus, хммммм.
И в условном английский словаре в худшем случае будет О(26 * |key|).
Коэф, конечно, коэф большой, но не настолько, чтобы это все медленно работало.
В целом, спасибо за ответы.
@@7IdE 26 в данном случае - это константа, следовательно её не учитываем, остается key
Сергей, добрый день! А вы не планируете создать курс по Java на степик? очень нравится ваша подача, хочу изучить новый язык
Спасибо! Пока не знаю
То есть нам нужно ещё хранить структуру для хранение веток дерева
Так как я понял здесь нет только левого и правого потомка
К тому же могут быть ключи с похожи значениями 'ror', 'or' и их уже запишем в разных ветвях. В чём же преимущество?
Да, все верно, нужно в каждом узле хранить ссылки на всех потомков. Особенность дерева - быстрый выбор всех потомков по некоторому префиксу.
Здравствуйте я бы хотел попросить вас сделать курс по q обучению
!
What's PL?
Вроде все понятно)