Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 57
Текст из файла (страница 57)
Задана произвольнаяя п|кледователькасть аз и элементов, выбранных аз мнажест»а, на кагором имеегсн некоторый естественный порндок. Необходимо переупорядочнть задвинув последа»ательнасть в том же естественном порядке. Алгоритм сортировки может относиться непосредсгпеано к поз»циам данных н перезаписи нх в памяти, а может н не затрагивать позиции данных, а оперировать тоаько с некоторыми привязанными к ннм параметрами Данные сортнруютсп персу»ар»дочи»а»нем списка непрямых адресов. Сортировка переупорядочиванием адресов полезна в тех случаях, когда объем данных в каждой позиции сам па себе очень велик.
Предположим, что с каждой позицией данных сааза» некоторый целочисленный параметр, п необходимо упорядочить поз»цып ланных так, чтобы целочаслсн»ый параметр менялся от своего наыбольшего значения к нанменьшему. Любая задача сортировки может быть сформулирована в таком виде. зщ Зэо Гл. !О. Внстзы ашорипы, щ»выезне н сшзтегвя аубинз»аиня !03 Пщр лез р р Нанвная пронедура сортнровка состоит в просмотре одной поаипии за другой в выборе той, которой соответствует наибольшее заачение параыетра. Затем так же «росматрнваются оставпшеся новация н н ходится та из них, которой соответств)ет наабольпгее знзчение параметра.
Это продолжается до тех пор, покз не буд)т рассартнрованы все позиция. В повседневной жизня, когда и мала. это вполне удонлетворкшльная процедура. Однако, среднее число шагов в ней пропорционально п . Для сортировки большнх списков камна действовать намного лучше. Хорашне алгоритмы сортировки основываются на делении списка пополам н дублирпванин. Одним из янх является алгорнтм шршпроеко слиянием, его счожность пропорциональна велнчлпе и Ьй, л. Разобье»г сонсак нз и позиций данных на две полавяны н упорядочнн каждую из ннх. Из этих упорядоченнык спнсков половив организуем общей упорядоченный списпк, слнвая нх вместе па следующему правнлу. Сравним верхние элементы в обоих списках.
Выберем нз ннх тот, который соответствует ббтьшсм) значению параметра, к размести»» его в качестве следующей пшкцня обьелнненного списка, выбросив иэ той половины, где он находился раньше. Так как каждая познцня попадает а обьеднненный спвсок после операцни срзвнення. то в общей сложноггя прядется сделать п сравненнй. Следовательно. сложность Сфп) алгоритма сортировкн слияннем описывается ре- курсией Эта ргкурсня лает оценку сложностн для алгарнтма сортировки слиянием С (л] < л 1од, л.
Так как нмеется только адно значеняе аргумента, прн котором здесь выполняется равенства,то при слкяанв некоторые сравнення не нужны, так что алгоритм можно аемнаго улу'»шить Тем не менее, мы полпгаем, что эта оценка является достаточно точной. И»геются другпе саособы разбиечня зздвчн сортнровкн В алгорктме «бысшрой сортировки» случайно выбирается один аз пара»»строе данных в качестве основы для разбиения спнсна. Харантервстнкн такого алгоритма иваяются случайными велпчннами, достаточно хороши»гн з среднем, но очень медлепнымн в наихудшах случаях. Так квк в алгоритме быстроз сортировки параметр разбвсння списка выбярается непосрсьственно яз данных, то этот параметр должен быть случаен В противном случае можно было бы построить тестовый сппсак, длн которого «быстрый алгорнтм» оказался бы очень плохим Например есле в качестве параметра разбиення списка всегда выбирать первый вход данных, то «бы- стрый алгорнтм» буды сортнровать список чрезвычайно медленно.
Быстрый алгоритм» работает следующим образом. Выберем случайно нз данных некоторый элемент с параметром а Все данные, за нсключеннеы а, разделим на два подмножества: те Ланные, параметр которых меньше з, и те данные, параметр которых не »~еаьше а. Упорядоп»м каждое из этих подмножеств я соединим вх в один список, расположнв позндню о между нина. Каждое из двух подмножеств упорядочивается по таком, же правнлу. Два сп ока, на которые разбивается исходный список, садер«сат по п — ! — » к » элементов, где ! — случайная величава, равновероятно распределенная на множестве (О, , л — 1) Слоя»вость форыировавкя этих множеств пропорцнональна и. Средняя сложность сортировки исходного списка из л тачек равна С(п) — Ал ! — ~~» С(»)-(- — ~ С(л — ! — »), где А — некоторая яонстанта.
Для я ) 2 это приводит к слелующей рекурсивной формуле лля сложности С (и) алгарнтма «быстрой ортнрозкн»: — 1 С(п) —. Ап-1- — ~ С(!) »=з прн начальных условиях С (О! = С (Ц = О. (Иногда предпочнтаап полагать С (О) к С (1) аекоторымк матыма константамн, но это мало что меняет н никак не влияет на асимптоткку сложаостн.) Покажем, что прн и ) 2 величина С (и) меньше, чеы 2Ап )ой п Доказательство проведем нндукцяей; предположим, что для всех ! < и величина С (») меньше, чем 2А»)п, !. Это справедливо для л =- 2. Тогда С(л)(Апф — ~~»»1п,г.
»=» Гзк как функция !)п, » выпукла, то правую часть можно огра внчить еелнчнной вида С (п) ( Ап -)- — ) х!п, хба. 4А Г Следовательно, С(п)(Ал .1- — (" "'" — — "~ .=2Ал1п,л зкт Гл. !с. Бм«грие 22 срэ и, с«наживи« ш р« гээ дгеляроз« зя Средняя характеристика алгоритма «быстрой сортировки» асимптатически лучше средвей характеристики алгоритма сортировки слиянием, но в наихудшем случае характеристика становится намного хуже. 10.4.
Рекурсивное быстрое преобразование Фурье по основанию два Камиле«снов преобразование Фурье по основанию два опре- деляется форыулай — ! Уь= ~ и'эао й=б, ..., л — 1, где л = 2", ш — пелое число и ч — вектор с комплексными кампо. нентами. В гл. 4 мы интересавалнсь построением алгоритмов, представляющих собой малый пакет уравнений, непосредственное применение которых позволяет вычислить преобразование Фурье радиуса два. Этот способ очень подходит для длин л, равных 8 или 18, намажет оказаться неподходящим при больших и. В на- стоящем параграфе мы выпишем алгоритм по основанию два в рекурсивной фарые.
Входные даннме в комплексы>м виде мм > выбираем потому, что прв и = 32 и более эта форма алгоритма применительно к комплекснмм данныи зффентввнее, чем двойное использование БПФ-алгоритма для вещественного входа. Так же, как и в гл. 4, воспользуемся методом Винограда для разбиения вычисления преобразования Фурье на отдельное вы- числение компонент с четными индексамк и комвонеит с нечет-, ными нндексаин. Для обрабики «омпонент с четнымн индеисами, заменим й на 23 и запишем 11 — ! Уы= 2э' (с>+а!т !з)им", й=-б, ..., и/2 — !. >-е Мы получили я/2-точечное преобразование Фурье нового вектора, иамнанентм «старого равны Ш -1- а!4. >2, так что для их вычисле- ния требуется и/2 комплексных сложений.
Для обработки компо- нент с нечетными индексами заменим й на 23 + 1 и запишем >2 — 1 !2 — ! у Ч' а Фи!мч.ц ! 5; е и!2>еп!м.ю> 1-э 1-2 = О, ..., и/2 — !. Этн две суммы будут рассматриваться отдельна. Для их сочета- ния потребуется еще л/2 комплексных сложений. !с« Рштр БПФ ш ! е и 22 В первой сумме выписанного уравнения необходима вычислять только первые компоненты для й = О, , л/4 — 1, так как в дальнейшем они повторяются. Эти «омпаие!Пы представляют собой (л/4).точечное преобразование Фурье вектора с компоиентамн амм", для вычисления последнего вектора требуется (314) и — 8 вещественных умножений (так каи эта вычисление содержит л/4 — 4 «омплексных умножений, каждое из которых мажет быть выполнено с греми вещественныма умножениями, и двз комплексных умножения, для вычисления «аищога из которых нужно только два вещественных умиожеяня) н столько же сложений.
Основкая часть рассуждений связана с вычислением промежуточного результата, >2 — 1 !и„= Е а«>„и>2!чо!ме!>, й.- О, ..., л/2 — !. Так иак порядок элемента и равен л, то вычисления в показателе степени должны проводиться по модулю л, где л =. 2". Все эти вычисления представляют собой умножения вечетных чисел по модулю 2". Согласно теореме 5.1.8, относительна оперзции умножения па модулю 2 множества вечетных чисел образует группу, изаморфную группе 32 Х ху и, следовательно, имеет две абразующие.
В качестве таких образующих можно выбрать 3 и — 1; тогда множество показателей степени образует мультипликативную группу (3' ( — 1)': ! = О, ..., 2 — ' — 1; !' — — О, !1, групповой операцией в которой является умножение по модулю 2 . На входных и выходимх индексах это задает соответственно подстановки 21Ф ! — з ( — Пг и зйФ(= з- ( — !)-'. При таком представлении индеисов предыдущее уравнение при. водится к виду !,.,=Е Е а. "'" ' У=О,), 1 — Э 1-2 где элементы 1...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
