Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Алгоритмы Обратить разреженных симметричных матриц http://www.cyberforum.ru/algorithms/thread1100027.html
Здравствуйте, У меня есть следующая задача: развести симметричную матрицу уплотняется распространение Cathill-McKee, расположенный в группе выше главной диагонали, только ненулевой каскадной зоне....
Алгоритмы Какую следует использовать нейронную сеть для прогнозирования Добрый день! Требуется информация, какую следует использовать нейронную сеть для прогнозирования? Слышала их о таких как: хопфилда, кохонена и.т.д. но какая именно подходит для решения такого рода... http://www.cyberforum.ru/algorithms/thread1099606.html
Как найти время работы алгоритма, по заданным значениям? Алгоритмы
Пусть время работы алгоритма T(N)=O(f(N)). Если X элементов обрабатывается за Y мсек., то во сколько раз следует ожидать увеличения времени выполнения при обработке Z элементов. f(N) = N2, X =...
Алгоритм решения задачи Алгоритмы
Всем привет! есть задача : Растет Роща реликтовых деревьев.Для их защиты требуется обнести рощу забором. Но для обеспечения доступа к остальной территории заповедника площадь участка, окруженного...
Алгоритмы Как вырезать мусор и все знаки препинания со строки не трогая мультибайтовые символы типо китайского иероглифа http://www.cyberforum.ru/algorithms/thread1098947.html
Есть задача создать чпу из тайтла но тайтл может содержать в себе все кроме этих символов < > Нужно составить ключевые слова с тайтла не используя знаки препинания. Главная проблема состоит в том...
Алгоритмы Сложение отрицательных чисел в дополнительном коде Скажем, 10100010 + 11110001 Получается переполнение. что с этим в итоге делать? подробнее
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
20.02.2014, 13:45 0

Поиск максимального элемента в массиве методом "разделяй и властвуй"

20.02.2014, 13:45. Просмотров 2353. Ответов 4
Метки (Все метки)

Ответ

Цитата Сообщение от SrgKord Посмотреть сообщение
Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его элементов на предмет превышения значения одной переменной над значением другой, с последующей записью этого значения в последнюю переменную.
А задача стоит описать этот алгоритм с применением метода "разделяй и властвуй". Вот я и думаю, а что тут делить? Итак код в двух строчках.
На какие две "еще более простые задачи" можно разделить эту задачу?
А этот массив случайно не обладает никакими свойствами ? Например, числа сначала возрастают, потом убывают, или еще какие свойства.
А то если это "обычный" массив с неизвестным поведением, то я не вижу как можно применить "разделяй и властвуй" с большим выигрышем.
Цитата Сообщение от Eldies Посмотреть сообщение
Еще можно применить sqrt-декомпозицию, когда массив из N элементов разделяется на http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N} частей, максимум каждой части просчитывается заранее и где-нибудь хранится. При изменении какого-нибудь элемента массива, перерассчитывается максимум соответствующей части массива, а максимум во всем массиве можно теперь искать всего за http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N} операций.
Я тут почеркал на листочке и посмотрел разные описания. Я вижу, что sqrt (и аналогичные) декомпозиции хороши при долговременной работе с массивом при операциях для однотипных результатов (сумма/максимум/минимум), но я не могу увидеть реальный выигрыш при использовании такого метода разово.

Вот, например, возьмем массив размера 81 и разобьем его на sqrt(81) = 9 частей
в каждой части мы для поиска локального максимума мы сделаем 8 сравнений и от 1 до 8 присваиваний
аналогичный цифры для поиска глобального максимума
Итого получаем 8*9+8 = 80 сравнений и от 10 до 80 присваиваний. Аналогичные цифры при прямом поиске.

Направь мой взор дабы узрел я истину.

Вернуться к обсуждению:
Поиск максимального элемента в массиве методом "разделяй и властвуй"
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.02.2014, 13:45
Готовые ответы и решения:

Методом "разделяй и властвуй" построить башни
Всем привет, последняя задачу которую нужно решить) Есть бесконечное количество блоков размера...

Методом "разделяй и властвуй" посчитать задания
Тема больше не актуальна Всем привет, снова мучаюсь с задачей вот уже пару дней. Ввод: ...

В каких случаях лучше использовать алгоритм "разделяй и властвуй"?
Подскажите, в каких случаях лучше использовать алгоритм разделяй и властвуй? Как оформить этот...

Разделяй и властвуй: сумма произведений попарных элементов массивов
Всем привет. Есть задача. Дан массив А из 150 чисел, который начинается с 2 и каждый следующий...

Поиск максимального паросочетания в задаче "Испорченный паркет"
Привет всем! Прошу помощи. Есть задача &quot;Испорченный паркет&quot;. Условие задачи следующее: Пол в...

4
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru