Декомпозиционный алгоритм для поиска наибольшего элемента

@Andreyphisicist · Регистрация: 24.02.2015

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

Добрый день. Помогите пожалуйста разобраться с одной задачкой. Задачка из книги А.Левитина "Алгоритмы: Введение в разработку и анализ". Задачка 4.1.1.

4.1.1. а) напишите псевдокод декомпозиционного алгоритма для поиска наибольшего элемента в массиве из n чисел.

б) Какими будут выходные данные алгоритма, если наибольшее значение имеют несколько элементов?

в) Напишите рекуррентное соотношение для количества сравнения ключей, выполняемых алгоритмом.

г) Сравните созданный вами алгоритм с алгоритмом для решения указанной задачи, основанным на грубой силе.

Решение:

a) Псевдокод декомпозиционного алгоритма (Возможно я неправильно выделил псевдокод. Просто я не нашел как правильно его выделять).

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Алгоритм Max2 (A[l...r])
 
if l=r 
   return A[l]
 
else 
   temp1 <- Max2(A[l...(l+r)/2])
   temp2 <- Max2 (A[(l+r)/2...r])
   
   if temp1 >= temp2 
      return temp1
 
   else 
      return temp2

в)

$https://www.cyberforum.ru/cgi-bin/latex.cgi?C(n)=2C(n/2) + n - 1<br />$

Поскольку $https://www.cyberforum.ru/cgi-bin/latex.cgi?a=2, b=2, d=1$ , то согласно основной теореме

$https://www.cyberforum.ru/cgi-bin/latex.cgi?C(n) \in \Theta (nlogn)$

г) Алгоритм на основе грубой силы имеет класс эффективности n, поэтому он будет эффективнее чем данный алгоритм.

@Andreyphisicist · 20.07.2015, 18:06 **[ТС]**

Ну это да. А мы с Вами подсчитали количество сравнений C(n) = 2n - 1 для сравнений l == r. Правильно я понял?

Добавлено через 2 минуты
Просто я немного запутался и хочу понять какие сравнения мы считали с Вами.

@Shamil1 · 20.07.2015, 20:45

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

Правильно я понял?

Мы с Вами посчитали для всех сравнений... но неправильно посчитали. Хотя, для сравнений l == r так и получается: 2n - 1.
А всего получается 3n - 2.

@Andreyphisicist · 22.07.2015, 18:44 **[ТС]**

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

А всего получается 3n - 2.

Да, мне тоже так кажется.

Во всех рекурсивных алгоритмах, которые я смотрел в книге Левитина обычно границы сравнений не учитывали и оценивали эффективность именно по количеству основных операций.

Вот у меня поэтому и возник вопрос, надо ли вообще сравнение l == r учитывать.
Т.е. оценить только количество сравнений temp1 >= temp2 и взять начальное условие C(1) = 1.

@Shamil1 · 22.07.2015, 19:10

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

Вот у меня поэтому и возник вопрос, надо ли вообще сравнение l == r учитывать.

Я не знаю.
По-моему, всё равно. (а в попугаях я значительно длиннее)

Если сравнение l == r не учитывать, то начальное условие будет C(1) = 0. Оно не "берётся", а вычисляется.

Новые блоги и статьи Все статьи Все блоги /
Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .	Цена ошибки DevAlt 23.08.2026 Человек я беспокойный и потому заинтересовался OCaml, в чате форсили функторы модулей как суперфичу. Пытаясь отдуплить концепт, наткнулся на тутор с простым примером. А главный принцип обучения от. . .
Сегодня суббота, 22.08.2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. zorxor 22.08.2026 Сегодня суббота, 22. 08. 2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. Кто Я, откуда Я пришел и куда Я иду? Эти вопросы не оставляют меня ни на секунду. Жизнь на планете Земля. . .	Жизня: рисунок укладки багажа, сделанный клодом anaschu 21.08.2026 Сделал 15 снимков, он по снимкам сделал схему.	Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .

@Andreyphisicist 0 / 0 / 0 Регистрация: 24.02.2015 Сообщений: 29
	20.07.2015, 18:06 [ТС]
	Ну это да. А мы с Вами подсчитали количество сравнений C(n) = 2n - 1 для сравнений l == r. Правильно я понял? Добавлено через 2 минуты Просто я немного запутался и хочу понять какие сравнения мы считали с Вами. 0