За доту и доку респект

@user-yg4no8qb3z

Жыл бұрын

Зашёл в комменты только ради этого)

Спасибо большое, смотрю видеоуроки на перёд по своему предмету в ВУЗе. Очень доходчиво объясняете материал. Жаль, что видео такое короткое, я бы ещё послушал.)

Отличное видео! Спасибо Вам за эти занятия!

Я в шоке от количества дельных роликов на этом канале Сергея.

Здравствуйте я бы хотел попросить вас сделать курс по q обучению

Сергей, добрый день! А вы не планируете создать курс по Java на степик? очень нравится ваша подача, хочу изучить новый язык

@selfedu_rus

Жыл бұрын

Спасибо! Пока не знаю

Где-то я уже видел этот видос. :D Но меня мучает вопрос: почему О(|key|)? Если я правильно понял, то |key| - это модуль ключа, т.е. длина(видимо, по аналогии с векторами). То есть, это тот же О(n), где n - длина ключа? Если это так, то у меня вопрос: а почему это тут такая сложность? Ведь нигде нет ограничений на то, каким должно быть дерево и сколько у каждого узла может быть детей. Это значит, что у нас может быть дерево, где будет корень с M детей(все 1-буквенные). И предположим, что у дерева будет строго 1 уровень в глубину. Но ведь в таком случае получится, что для для нахождения ключа нам придется перебрать М вариантов в худшем случае. И тогда сложно будет не О(|key|), а О(М). И, кажись, это будет справедливо для каждого уровня: на каждый символ в ключе нам придется перебирать все ключи на текущем уровне дерева. Разве нет?

@selfedu_rus

Жыл бұрын

Все верно расписали! Взял из теории по префиксному дереву. Вероятно, там полагают длину ключа переменной, а множества проверок - некоторой постоянной опреацией, в итоге она выносится на O большое и остается только длина ключа. Но этом мои догадки. Главное, конечно, понимать как происходит поиск в деталях.

@7IdE

Жыл бұрын

​@@selfedu_rus, кстати, да, это хорошее замечание про константу. Там реально все будет сводиться О(n), т.к. мы предполагаем, что дерево уже сформировано и не будет меняться от ключа к ключу. Об этом я как-то не задумался. Но, в любом случае, такая структура данных, на первый взгляд, может оказаться крайне неэффективной - как раз-таки из-за этих констант.

@selfedu_rus

Жыл бұрын

@@7IdE часто она применяется для слов, и максимум число потомков - размер алфавита языка, т.е. не очень много, ну и выбрать всех потомков по префиксам - это тоже классная фишка этого дерева )

@7IdE

Жыл бұрын

​@@selfedu_rus, хммммм. И в условном английский словаре в худшем случае будет О(26 * |key|). Коэф, конечно, коэф большой, но не настолько, чтобы это все медленно работало. В целом, спасибо за ответы.

@alexanderkrutko644

Жыл бұрын

@@7IdE 26 в данном случае - это константа, следовательно её не учитываем, остается key

То есть нам нужно ещё хранить структуру для хранение веток дерева Так как я понял здесь нет только левого и правого потомка К тому же могут быть ключи с похожи значениями 'ror', 'or' и их уже запишем в разных ветвях. В чём же преимущество?

@selfedu_rus

Жыл бұрын

Да, все верно, нужно в каждом узле хранить ссылки на всех потомков. Особенность дерева - быстрый выбор всех потомков по некоторому префиксу.

What's PL?

Вроде все понятно)

!