Публикации по теме 'divide-and-conquer'
Алгоритмы: бинарный поиск
Бинарный поиск является эффективным методом поиска. Временная сложность варьируется от O (1) до O (log n).
Шаг 1 . Назначьте переменные первому и последнему элементам массива.
Шаг 2 . Используйте цикл while для перебора входного массива.
Шаг 3 . Проверьте, равно ли среднее значение, больше или меньше целевого значения. Если равно, вернуть значение. Если бы это была первая итерация, мы бы искали за O(1). Если значение nums[middle] больше целевого, конечное значение будет..
Вопросы по теме 'divide-and-conquer'
время работы алгоритма changetoBinary?
Я разработал алгоритм для преобразования степени 10 в двоичную, предполагая, что n является степенью 2. Я использовал метод Гаусса, чтобы использовать быстрое время работы этого замечательного метода. Для этого я делю n на 2 и отправляю его в метод...
59 просмотров
schedule
19.05.2024
разница разделяй и властвуй и разветвляйся и присоединяйся
В С++, в чем разница между разделяй и властвуй и разветвляй и присоединяйся? Является ли вилка и соединение особым случаем «разделяй и властвуй», потому что вилка и соединение применяются только в параллелизме? Спасибо!
1159 просмотров
schedule
23.11.2022
Покупка и продажа акций с временной сложностью O( n log n )
РЕДАКТИРОВАТЬ: Я ценю помощь от вас обоих, но я должен оставаться с границей полноты времени O ( n log n ) и должен использовать метод «разделяй и властвуй» с бинарной рекурсией. Я не очень ясно выразился в начальном посте
У меня есть...
1770 просмотров
schedule
31.10.2023
Какой алгоритм лучше всего подходит для работы с параллельными процессорами?
Если бы у меня была машина с несколькими процессорами и я пытался бы решить огромную проблему, какой алгоритм лучше всего подходил бы для решения этой задачи?
Динамическое программирование, жадность или алгоритм «разделяй и властвуй»?
84 просмотров
schedule
06.05.2024
Разделяй и властвуй - Минимум монет - Возврат монет в виде массива
Ниже приведено грубое решение проблемы минимальной раздачи монет. Требуется int change, то есть изменение, которое необходимо внести, и массив номиналов монет. Он возвращает минимальное количество монет, необходимое для внесения этого изменения....
498 просмотров
schedule
25.11.2023
Размер самого большого сбалансированного бинарного поддерева
Я пытаюсь создать алгоритм «разделяй и властвуй», который при запуске в корне двоичного дерева возвращает размер наибольшего сбалансированного двоичного поддерева, содержащегося в дереве, или, другими словами, размер наибольшего возможного поддерева,...
687 просмотров
schedule
28.02.2024
Шахматную доску ???? × ???? нужно разрезать на ????·???? единичных квадратов.
Шахматную доску ???? × ???? нужно разрезать на ????·???? единичных квадратов. На каждом шаге вы можете сделать либо один горизонтальный, либо один вертикальный разрез. Первый разрез разделит плату на две части; после этого каждый разрез разделяет...
639 просмотров
schedule
25.05.2024
С++ Разделяй и властвуй алгоритм умножения матриц слишком медленный
Я хотел бы попросить вас о помощи. Я реализовал алгоритм «разделяй и властвуй» на C++. Работает нормально, но очень медленно. Матрица 512x512 рассчитывается как 90 секунд, что неприемлемо по сравнению с 0,4 с наивным алгоритмом. Не могли бы вы...
142 просмотров
schedule
09.04.2024
Найдите максимальный продукт, используя рекурсию
Я видел вопрос, и мне интересно, можно ли решить его с помощью рекурсии. Это происходит следующим образом:
Напишите алгоритм, который при наличии массива входных данных находит максимальное произведение из этих входных данных. Например:...
472 просмотров
schedule
29.12.2023
Наименьшее подмножество с суммой больше или равной k
Я пытаюсь найти алгоритм «разделяй и властвуй» для решения этой проблемы за O (n), но ничего не нашел. учитывая массив A и заданное значение k. найти наименьшее подмножество с суммой, большей или равной k. Может кто подскажет, как начать решать...
63 просмотров
schedule
29.05.2024
