В CLRS , третьем издании, на стр. 155, указано, что в MAX-HEAPIFY, "the worst case occurs when the bottom level of the tree is exactly half full" Я предполагаю, что причина в том, что в этом случае Max-Heapify должен «плавать вниз» через...

Во Введении в алгоритмы P657, 3-е издание, говорится: Критический путь - это самый длинный путь через dag, соответствующий наибольшему времени для выполнения любой последовательности заданий. Таким образом, вес критического пути обеспечивает...

В CLRS ( Introduction to Algorithms Cormen, Leiserson, Rivest и Stein) для функция f ( n ) = an 2 + bn + c Они сказали Предположим, мы берем константы c 1 = a /4, c 2 = 7 a /4 и n 0 = 2·max(| b |/ a , √(| c |/...

Возможен ли жадный алгоритм для этой задачи. Я разработал для него алгоритм DP, но не уверен в жадном алгоритме для него. Пожалуйста, объясните, существует ли для него жадный алгоритм. Для тех, кто не знаком с проблемой: Есть 'n' действий...

Я читаю Введение в алгоритмы CLRS. В книге показан псевдокод для простого умножения матриц «разделяй и властвуй»: n = A.rows let c be a new n x n matrix if n == 1 c11 = a11 * b11 else partition A, B, and C C11 =...

Я пытаюсь решить упражнение 32.1-2 из книги CLRS, посвященное строковым алгоритмам, наивному поиску по шаблону. Предположим, что все символы в шаблоне P различны. Покажите, как ускорить NAIVE-STRING-MATCHER, чтобы он выполнялся за время O(n)...

Согласно определению, доступному в 3-м издании CLRS, односвязный ориентированный граф — это граф, в котором для каждой пары вершин (u,v) существует не более 1 уникального пути из u->v. Теперь в большинстве ответов, которые я прочитал, говорится, что...

CLRS говорит нам обменять A[r] на A[i] , где i — случайная величина между p и r. Однако, если бы я случайным образом выбрал переменную в качестве опорной в функции быстрой сортировки и обменялся значениями, какова теперь будет временная сложность?...

Как бы вы использовали дерево решений, чтобы доказать, что поиск в отсортированном списке из n элементов имеет нижнюю границу Omega (log n) с моделью, основанной на сравнении?

В книге Introduction to Algorithms есть строка под заголовком Анализ сортировки вставками , которая гласит: «Когда цикл for или while завершается обычным образом (т. е. из-за теста в заголовке цикла), тест выполняется на один раз больше, чем...

Учитывая следующий алгоритм линейного поиска (ссылаясь на индекс 1 как на индекс первого элемента в массиве элементов): found_idx = nil for i = 1 to A.length if A[i] == value found_idx = i return found_idx end-if end-for found_idx...

Мне трудно понять следующую лемму из CLRS: Пусть G — поточная сеть, s и t — узлы источника и стока, f — предпоток из s в t, а h — функция высоты на G. Тогда в остаточном графе G ф . Почему это?