Здравствуйте, да, правильно говорить не совсем так. Энтропия это не MSE, просто в головах людей энтропия — это та самая штука, которая считается в деревьях и по которому ищется разбиение, возможно это упростило переход к понимаю деревьев с MSE (надеюсь :)).
Знаем, что количество последовательностей равно определенному числу Каталана. Чтобы сгенерировать одну последовательность, нужно один раз пройтись по списку.
Следовательно, сложность равна число Каталана * длину списка.
В большинстве случаев на те, кто будет software заниматься — инфраструктура, БД, иногда могут и на другие позиции давать, например на ML-специалистов.
Однако есть одно но:
1) В чистом виде такие задачи встретятся далеко не факт (хотя разговаривал с чуваком, который в Яндекс собеседовался — попросили сгенерить все перестановки), в большинстве случаев будут несложные модификации таких задачек (например, сгенерить все перестановки строки).
2) Собес по алгоритмам — далеко не единственный собес, будет куча и других:)
Числа Каталана
Знаем, что количество последовательностей равно определенному числу Каталана. Чтобы сгенерировать одну последовательность, нужно один раз пройтись по списку.
Следовательно, сложность равна число Каталана * длину списка.
Однако есть одно но:
1) В чистом виде такие задачи встретятся далеко не факт (хотя разговаривал с чуваком, который в Яндекс собеседовался — попросили сгенерить все перестановки), в большинстве случаев будут несложные модификации таких задачек (например, сгенерить все перестановки строки).
2) Собес по алгоритмам — далеко не единственный собес, будет куча и других:)