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

@SrgKord · Регистрация: 14.02.2013

Author24 — интернет-сервис помощи студентам

Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его элементов на предмет превышения значения одной переменной над значением другой, с последующей записью этого значения в последнюю переменную.
А задача стоит описать этот алгоритм с применением метода "разделяй и властвуй". Вот я и думаю, а что тут делить? Итак код в двух строчках.
На какие две "еще более простые задачи" можно разделить эту задачу?

@Eldies · 19.02.2014, 00:27

Как вариант - разделить задачу на две задачи:
1) поиск максимума в первой половине массива
2) поиск максимума во второй половине массива
и сравнить найденное.
Метод применён)

Еще можно применить sqrt-декомпозицию, когда массив из N элементов разделяется на $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N}$ частей, максимум каждой части просчитывается заранее и где-нибудь хранится. При изменении какого-нибудь элемента массива, перерассчитывается максимум соответствующей части массива, а максимум во всем массиве можно теперь искать всего за $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N}$ операций.

@SrgKord · 19.02.2014, 00:37 **[ТС]**

А ведь этот вариант у меня в голове неоднократно возникал, но я его отвергал, как слишком... плоский, что ли. Но тут, пожалуй, ни чего лучше и не сделаешь =)

@wingblack · 20.02.2014, 13:45

Сообщение от SrgKord

Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его элементов на предмет превышения значения одной переменной над значением другой, с последующей записью этого значения в последнюю переменную.
А задача стоит описать этот алгоритм с применением метода "разделяй и властвуй". Вот я и думаю, а что тут делить? Итак код в двух строчках.
На какие две "еще более простые задачи" можно разделить эту задачу?

А этот массив случайно не обладает никакими свойствами ? Например, числа сначала возрастают, потом убывают, или еще какие свойства.
А то если это "обычный" массив с неизвестным поведением, то я не вижу как можно применить "разделяй и властвуй" с большим выигрышем.

Сообщение от Eldies

Еще можно применить sqrt-декомпозицию, когда массив из N элементов разделяется на $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N}$ частей, максимум каждой части просчитывается заранее и где-нибудь хранится. При изменении какого-нибудь элемента массива, перерассчитывается максимум соответствующей части массива, а максимум во всем массиве можно теперь искать всего за $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N}$ операций.

Я тут почеркал на листочке и посмотрел разные описания. Я вижу, что sqrt (и аналогичные) декомпозиции хороши при долговременной работе с массивом при операциях для однотипных результатов (сумма/максимум/минимум), но я не могу увидеть реальный выигрыш при использовании такого метода разово.

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

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

@Eldies · 20.02.2014, 17:03

Сообщение от wingblack

Я тут почеркал на листочке и посмотрел разные описания. Я вижу, что sqrt (и аналогичные) декомпозиции хороши при долговременной работе с массивом при операциях для однотипных результатов (сумма/максимум/минимум), но я не могу увидеть реальный выигрыш при использовании такого метода разово.

При разовом поиске максимума никакого выигрыша действительно нет.
Не зная, какая конкретно задача у ТС, предложил sqrt-декомпозицию, как метод, который
1) является реализацией "разделяй и властвуй"
2) приводит к выигрышу на немаленьком классе задач

@SrgKord 49 / 31 / 2 Регистрация: 14.02.2013 Сообщений: 677
		1
	Поиск максимального элемента в массиве методом "разделяй и властвуй" 19.02.2014, 00:02. Показов 6327. Ответов 4 Метки нет (Все метки) Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его элементов на предмет превышения значения одной переменной над значением другой, с последующей записью этого значения в последнюю переменную. А задача стоит описать этот алгоритм с применением метода "разделяй и властвуй". Вот я и думаю, а что тут делить? Итак код в двух строчках. На какие две "еще более простые задачи" можно разделить эту задачу? 0

@Eldies 93 / 85 / 40 Регистрация: 06.02.2014 Сообщений: 122
	19.02.2014, 00:27	2
	Сообщение было отмечено SrgKord как решение Решение Как вариант - разделить задачу на две задачи: 1) поиск максимума в первой половине массива 2) поиск максимума во второй половине массива и сравнить найденное. Метод применён) Еще можно применить sqrt-декомпозицию, когда массив из N элементов разделяется на $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N}$ частей, максимум каждой части просчитывается заранее и где-нибудь хранится. При изменении какого-нибудь элемента массива, перерассчитывается максимум соответствующей части массива, а максимум во всем массиве можно теперь искать всего за $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N}$ операций. 1

@SrgKord 49 / 31 / 2 Регистрация: 14.02.2013 Сообщений: 677
	19.02.2014, 00:37 [ТС]	3
	А ведь этот вариант у меня в голове неоднократно возникал, но я его отвергал, как слишком... плоский, что ли. Но тут, пожалуй, ни чего лучше и не сделаешь =) 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,037
	20.02.2014, 13:45	4
	Сообщение от SrgKord Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его элементов на предмет превышения значения одной переменной над значением другой, с последующей записью этого значения в последнюю переменную. А задача стоит описать этот алгоритм с применением метода "разделяй и властвуй". Вот я и думаю, а что тут делить? Итак код в двух строчках. На какие две "еще более простые задачи" можно разделить эту задачу? А этот массив случайно не обладает никакими свойствами ? Например, числа сначала возрастают, потом убывают, или еще какие свойства. А то если это "обычный" массив с неизвестным поведением, то я не вижу как можно применить "разделяй и властвуй" с большим выигрышем. Сообщение от Eldies Еще можно применить sqrt-декомпозицию, когда массив из N элементов разделяется на $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N}$ частей, максимум каждой части просчитывается заранее и где-нибудь хранится. При изменении какого-нибудь элемента массива, перерассчитывается максимум соответствующей части массива, а максимум во всем массиве можно теперь искать всего за $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N}$ операций. Я тут почеркал на листочке и посмотрел разные описания. Я вижу, что sqrt (и аналогичные) декомпозиции хороши при долговременной работе с массивом при операциях для однотипных результатов (сумма/максимум/минимум), но я не могу увидеть реальный выигрыш при использовании такого метода разово. Вот, например, возьмем массив размера 81 и разобьем его на sqrt(81) = 9 частей в каждой части мы для поиска локального максимума мы сделаем 8 сравнений и от 1 до 8 присваиваний аналогичный цифры для поиска глобального максимума Итого получаем 8*9+8 = 80 сравнений и от 10 до 80 присваиваний. Аналогичные цифры при прямом поиске. Направь мой взор дабы узрел я истину. 1

@Eldies 93 / 85 / 40 Регистрация: 06.02.2014 Сообщений: 122
	20.02.2014, 17:03	5
	Сообщение от wingblack Я тут почеркал на листочке и посмотрел разные описания. Я вижу, что sqrt (и аналогичные) декомпозиции хороши при долговременной работе с массивом при операциях для однотипных результатов (сумма/максимум/минимум), но я не могу увидеть реальный выигрыш при использовании такого метода разово. При разовом поиске максимума никакого выигрыша действительно нет. Не зная, какая конкретно задача у ТС, предложил sqrt-декомпозицию, как метод, который 1) является реализацией "разделяй и властвуй" 2) приводит к выигрышу на немаленьком классе задач 1

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

Решение