какое же огромное вам хочу спасибо я сказать, что обратили внимания на числа при объяснении бинпоиска по ответу, это дало главный толчок к пониманию данного типа бинпоиска мне
Понятно когда СНМ храним в виде дерева, мы каждым элементом подмножества ссылаемся на корень дерева, это быстро брать и поправлять если что. А когда нам надо смерджить два множества то есть дерева, это же будет долго потому что надо каждую ссылку в одном из деревьев менять, это считается ли долго и так ли как я понял объединять два дерева? Просто акцент на этом не сделан или я не заметил
Подскажите пожалуйста, когда мы хотим отсортировать массив при помощи кучи, но внутри одного массива, мы хотим преобразовать массив в кучу а потом пройти делая shift-down. Но разве цикл из sift-up делает из массива кучу?
I do not understand how is O( ✓n * log²(n) ) = O(n) I think it is greater than linear complexity. Example: If n=64, ✓n * log²(n) = 8 * 6² = 288 Am I missing something ? Please help
Looks like your solution of the bacteria problem is not a hammer, since it's very technic and requires a deep understanding of what is going on. Maybe even deeper than it was expected :D
На 14:40 непонятно, что значит "добавить b". Разве его не в верхнюю строку надо добавить? Просто выглядит так, словно вы отрезаете b из второй строки, хотя говорите при этом, что добавляете.
Почему на 11:11 именно сравнивается A[i-1] и B[i-1]? Почему не "Если A[i]==B[i]" И почему тогда наше d[i][j]==d[i-1][j-1]? Вот эти два момента вообще непонятны, и, соответственно, непонятно всё, что идет дальше.
Ну это все теоретические структуры данных, понятно что на практике нужно по-другому все делать. А с точки зрения теории интересно обойтись минимальным множеством доступных операций
Отличный канал, спасибо! Для интересующихся графами рекомендую свободно распространяемую электронную книгу «Графомания» (автор Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы: Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания на взвешенных графах: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона на взвешенных графах: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра на взвешенных графах: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (контур); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.
Hey pashka, Thanks for this wonderful tutorial. I had a query watching the video, hope you will answer: In partially persistent linked list, if we store a list of pointers at each node (based on version). Then the time complexity to add and remove would be O(1). Also the worst case time complexity of iteration will be Σlog(size(i)) for 1<=i<=n, where n is the number of nodes and size(i) is the size of ith node. We can observe Σsize(i) will be of order v (no of versions). The worst case doesn't seem like n*log(v) in this case. The worst case I could come up with was O(n + sqrt(v)*log(sqrt(v)) ) which is equivalent to O(n). Could you add your opinion here. Thanks
По теме графов рекомендую свободно распространяемую электронную книгу «Графомания» (Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы: Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания на взвешенных графах: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона на взвешенных графах: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра на взвешенных графах: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (контур); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.
