WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Пошук за ключем у масиві - Реферат

Пошук за ключем у масиві - Реферат

першому місці. Наприклад, за читання послідовності значень 3, 1, 2 створюються послідовності значень у масиві , , .
Узагалі, після читання k-1 елемента маємо відсортовану частину масиву A[1]A[2]...A[k-1]. Нове значення v порівнюємо зі значенням A[k-1]. Якщо A[k-1]>v, то значення A[k-1] зсуваємо на k-е місце. Після цього порівнюємо v зі значенням A[k-1]: якщо A[k-2]>v, то A[k-2] зсуваємо на (k-1)-е місце тощо. Коли за чергового порівняння A[i] m
C1 G(n) F(n) C2 G(n).
Така залежність між функціями позначається за допомогою знака "О":
F(n) = O(G(n)).
Для задання порядку зростання інколи користуються іншим означенням: функція F(n) називається функцією порядку G(n) за великих n, якщо , де C>0, C 2 маємо
0.5 n2 < n*(n-1) < n2.
Аналогічно неважко довести, що n3 + 100 n2 = O(n3) = o(n3.1) = o(2n), 100 logn + 10000 = O(logn) = O(lgn) = o(n).
Приклад 2. Складність алгоритму бульбашкового сортування tb(n)=O(n2), алгоритму лінійного пошуку - t1(n)=O(n), бінарного пошуку - t2(n)=O(logn)=o(n).
Тепер означимо поняття складності задачі. Алгоритми пошуку в упорядкованому масиві свідчать, що одна й та сама задача може мати алгоритми розв'язання з різною складністю. Неформально, під складністю задачі розуміють найменшу зі складностей алгоритмів її розв'язання. Іншими словами, задача має складність порядку G(n), якщо існує алгоритм її розв'язання зі складністю O(G(n)) і не існує алгоритмів зі складністю o(G(n)).
Наприклад, складність задачі пошуку в упорядкованому масиві визначається складністю алгоритму двійкового пошуку, тому й оцінюється функцією logn. Задача сортування масиву має складність порядку n logn. Доводити ці факти ми не будемо - можна подивитися, наприклад, у книгу [АХУ]. Але в наступному параграфі ми наведемо алгоритми сортування з цією оцінкою складності.
Задачі
5. Оцінити складність задачі
а) * про Ханойські вежі (підр.9.3); б) пошуку підмножини (підр.9.2).
6.* Оцінити складність алгоритмів сортування вибором та простими вставками (задачі 17.3, 17.4).
7.* Задача про неспадну підпослідовність. Задано n-елементний масив цілих, n<10000. Знайти:
а) максимальну довжину неспадних підпослідовностей значень масиву;
б) неспадну підпослідовність значень масиву максимальної довжини. Якщо таких кілька, то з них вибиpається та, що має найменшу суму елементів. Напpиклад, за масиву зі значеннями це буде .
Складність алгоритму повинна бути якомога меншою.
4. Ефективні алгоритми сортування
4.1. Сортування злиттям
В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву.
Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається - тоді решта іншої колони додається до нової.
Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m+s] - впорядкована ділянка довжини r. Наприклад,
Y … 1 3 … 13 2 4 … 88
… m m+1 m+s-1 m+s m+s+1 … m+s+r
Результатом злиття повинна бути ділянка довжини r+s у масиві X:
X … 1 2 3 4 … 13 … 88
… m m+1 m+2 m+3 … m+s+r
За дії означень (17.1) таке злиття двох ділянок у масиві Y у ділянку масиву X задає процедура
procedure mrg( var Y : ArT; m, s, r : Indx; var X : ArT);
var mr, k : Indx; i, j : Extind;
begin
mr := m + s; { mr - початок правої частини }
i := m; j := mr; { i та j пробігають ліву й праву ділянки масиву Y}
for k := m to m + s + r - 1 do{заповнення X[m], … , X[m+s+r-1]}
if i > m + s - 1 then
begin X[k] := Y[j]; j := j + 1 end else
if j > mr + r - 1 then
begin X[k] := Y[i]; i := i + 1 end else
if Y[i] < Y[j] then
begin X[k] := Y[i]; i := i + 1 end else
begin X[k] := Y[j]; j := j + 1 end
end
Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], … , A[n] копіюються в допоміжний масив B[1], … , B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1.
На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки довжиною 4. Нехай t=nmod4 - довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t.
Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n.
Розглянемо сортування злиттям масиву довжини n=11. Упорядковані послідовності в ньому вказуються в дужках , а пари таких, що зливаються, відокремлені ";":
< ; ; ; ; ; >, lp=1
< ; ; >, lp=2
< ; >, lp=4
< >, lp=8
, lp=16, lp n.
Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив.
За дії означень (17.1) такий спосіб сортування описується процедурою Mrgsort:
procedure Mrgsort (var A : ArT; n : Indx);
var B : ArT; lp, npp, cpp, bpp, tl : integer;
begin
lp := 1;
while lp lp then
mrg ( B, n - tl + 1, lp, tl - lp, A );
{ за tl = n : масив упорядковано на останньому кроці }
end
Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1 n/2, npp = 0, tl = n > lp,
і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.
Оцінимоскладність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k=r then exit;
m:=(l+r) div 2;
Mrgrec(A, B, l, m); Mrgrec(A, B, m+1,r);
mrg(A, l, m-l+1, r-m, B);
for k:=l to r do A[k]:=B[k];
end;
Ця процедура набагато коротше нерекурсивної процедури Merges, але виконання її довше. Власне сортування починається лише після повернення з викликів, у яких l=r, а це практично "середина дистанції".
Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.
Серйозним недоліком цього алгоритму є необхідність додаткового масиву такої ж довжини, як і в основного. За великих довжин можлива ситуація, коли на один масив пам'яті вистачає, а на два - ні. Розглянемо два алгоритми, позбавлені цього недоліку.
4.2. Піраміда, вона ж дерево
Уявіть собі, що ми розташували елементи масиву рядками, щоразу подвоюючи їх кількість: у першому рядку - перший елемент, у другому - елементи з індексами 2, 3, у наступному - 4, 5, 6, 7, далі 8, 9, 10, 11, 12, 13, 14, 15 тощо. Останній рядок може виявитися неповним. Наприклад, за кількості елементів n=12 маємо таку піраміду індексів:
1
2 3
4 5 6 7
8 9 10 11 12
Елементи цієї піраміди будемо називати вузлами.
Між вузлами проведемо стрілки: від 1 - до 2 та 3, від 2 - до 4 та 5, від 3 - до 6 та 7 тощо, тобто від кожного вузла k до 2k та 2k+1, де k
  • <<
  • Перша Попередня 1 2 3 4 Наступна Остання
  • >>
  • Loading...

     
     

    Цікаве