Поняття компонента в програмуванні - з другим та записується або на третє місце, або витісняє значення з другого місця �...

Реферат - Поняття компонента в програмуванні

з другим та записується або на третє місце, або витісняє значення з другого місця на третє та порівнюється з тим, що на першому місці. Наприклад, за читання послідовності значень 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. Задача про неспадну підпослідовність.

Задано n-елементний масив цілих, n m + s – 1 thenbegin X[k] := Y[j]; j := j + 1 end elseif j > mr + r – 1 thenbegin X[k] := Y[i]; i := i + 1 end elseif Y[i] < Y[j] thenbegin X[k] := Y[i]; i := i + 1 end elsebegin X[k] := Y[j]; j := j + 1 endend Тепер розглянемо сортуваннямасиву 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 < n dobegin B := A; { копіювання } npp := n div (2*lp); { кількість пар ділянок } tl := n mod (2*lp); { довжина залишку } for cpp := 1 to npp do { cpp – номер пари } begin bpp := (cpp – 1)*2*lp + 1; { індекс першого елемента лівої ділянки пари} mrg ( B, bpp, lp, lp, A ); end; { обробка залишку } if tl > 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 a[c[ll]].y) or (tp.y > a[c[rr]].y)or not( (tp.x>a[c[ll]].x)and(tp.x a[c[rr]].y)or not( (tp.x>a[c[ll]].x)and(tp.x.

Список використаної літератури:

3. Інформаційні системи. – К., 1989р.

4. Підручник Інформатика. – К., 1999р.

Сторінки: 1 2