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

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

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

Пошук, сортування та поняття складності - Реферат


Реферат на тему:
Пошук, сортування та поняття складності
1. Пошук за ключем у масиві
1.1. Лінійний пошук
Читачеві колись доводилося шукати своє прізвище в списках, надрукованих не в алфавітному порядку? Або уявіть собі словник на 100 тисяч слів, розташованих там без упорядкування за алфавітом. Потрібне слово шукати там доведеться довго. Дуже довго. Звичайно, якщо воно випадково не потрапило в самісінький початок. А якщо в кінець чи середину? А пошук слова в "нормальному" словнику займає чомусь кілька секунд незалежно від його розташування там.
У цьому параграфі ми наведемо два алгоритми. Перший описує пошук "підряд" у невпорядкованій послідовності, другий - той пошук, до якого ми звикли, шукаючи слова в словниках. Замість слів розглянемо цілі значення елементів масиву. Тип значень може бути й іншим - головне, щоб їх можна було порівнювати.
Нехай елементи масиву A[1], A[2], … , A[n] та змінна key ("ключ") мають той самий тип T. Пошук за ключем полягає в пошуку номера i такого, що A[i]= key. За відсутності такого номера результатом будемо вважати 0. Нехай діють означення
const maxn = 1000;
type T = integer;
Indx = 1 .. maxn; (17.1)
ArT = array [Indx] of T;
Подамо розв'язання задачі функцією
function srcseq ( var A : ArT; n : Indx; key : T) : integer;
var i : integer;
begin
i := 0;
while ( i <= n ) do
if A[i] key then i := i + 1 else break;
{ i = n + 1 або A[i] = key }
if i < n + 1 then srcseq := i
else srcseq := 0
end
З'ясуємо, яким чином час пошуку за цим алгоритмом залежить від кількості n елементів масиву. Узагальнимо присвоювання та операції над значеннями скалярних типів (порівняння, додавання, множення тощо) терміном елементарна дія. Будемо вважати, що на виконання кожної елементарної дії витрачається скінченний обмежений проміжок часу, незалежний від конкретних операндів. За такого припущення час виконання програми (підпрограми) прямо пропорційний кількості елементарних дій у процесі виконання.
Очевидно, що кількість елементарних дій при виконанні функції srcseq прямо пропорційна кількості порівнянь A[i]key. В найгіршому випадку з ключем порівнюються всі елементи масиву. Звідси максимальна кількість дій та найбільший час виконання функції прямо (лінійно) пропорційні n, і найбільший час пошуку t1 є лінійною функцією від кількості елементів масиву. Описаний спосіб пошуку називається лінійним. Лінійну залежність часу від кількості елементів, тобто довжини n, будемо позначати символом "O": t1 = O(n).
1.2. Дихотомічний пошук
Тепер опишемо так званий дихотомічний пошук у "нормальному словнику". Ми розкриваємо словник приблизно в його середині. Якщо слово повинно бути в словнику далі, то шукати треба лише в другій половині словника. Його середина стає для нас початком, і ми розкриваємо його на середині другої половини. Аналогічно, коли слово повинно бути в першій половині, ми залишаємо для пошуків лише її. Отже, кожне заглядання в словник поділяє "простір пошуку" на дві половини й зменшує його приблизно вдвічі. Звідси й назва, оскільки дихотомія - це поділ на дві половини. Такий пошук ще називають двійковим, або бінарним.
Нехай значення елементів масиву упорядковані за зростанням, тобто A[1] A[2] … A[n] (кажуть, масив відсортований). Опишемо дихотомічний пошук такою функцією:
function srcbin ( var A : ArT; n : Indx; key : T) : integer;
var i, hb, lb : integer;
begin
lb := 1; hb := n;
i := (lb + hb) div 2;
while (lb key
then hb := i - 1 { key може бути лише ліворуч від A[i] }
else lb := i + 1; { key може бути лише праворуч від A[i] }
i := (lb + hb) div 2
end;
{ lb >= hb або A[i] = key }
if (i=0) or (i=n+1) then srcbin := 0 else
if A[i] = key then srcbin := i else srcbin := 0
end
Виконання тіла циклу while вимагає сталого числа елементарних дій незалежно від значень змінних A, key, i, lb, hb. Звідси загальна кількість дій прямо пропорційна кількості повторень тіла циклу while. Але за кожного повторення різниця hb-lb зменшується принаймні у два рази. Спочатку hb-lb = n - 1, тому виконань тіла циклу не більше ніж log2n , звідки час виконання функції t2 = O(log2n). Ця пропорційність зумовлює ще одну назву описаного пошуку - логарифмічний.
Чим більше n, тим більше відношення n до log2n. Наприклад, за n=10000 це більше 500. Коли треба відшукати значення один раз, можливо, комп'ютер упорається досить швидко і за лінійним алгоритмом. Але в реальних задачах доводиться шукати за ключем багаторазово, і різниця між лінійним і двійковим пошуком стає дуже відчутною.
Для двійкового пошуку необхідний відсортований масив, тому в наступному підрозділі почнемо розглядати способи сортування масивів.
Існує кілька інших способів швидкого пошуку в масивах. Їх докладне описання є в книзі [Кнут, т.3].
2. Бульбашкове сортування
Розглянемо найпростіший (і найгірший з точки зору витрат часу) спосіб сортування масиву. Нехай A[1], A[2], ... , A[n] - масив із довільними значеннями елементів. Порівняємо A[1] і A[2]: якщо A[1]>A[2], то поміняємо їхні значення місцями. Потім порівняємо A[2] і A[3] та за необхідності обміняємо їхні значення. В результаті A[3] має найбільше значення серед A[1], A[2], A[3]. Продовжимо такі порівняння та обміни до кінця масиву:
для всіх i від 1 до n-1 виконати
якщо A[i]>A[i+1], то
значення A[i] та A[i+1] обмінюються.
Якщо значення елементів розглядати як розміри бульбашок, то ці порівняння та обміни схожі на те, як більші бульбашки відтісняють менших униз і спливають нагору. Тому цей метод називається бульбашковим сортуванням. У результаті найбільша бульбашка стає верхньою, тобто останній елемент A[n] має найбільше значення. Наприклад, послідовність значень перетвориться на .
Далі почнемо все спочатку і перемістимо друге за величиною значення до передостаннього елемента A[n-1], перетворивши, наприклад, на . Потім третє за величиною значення перемістимо до A[n-2] тощо. Останній крок складається лише з порівняння A[1] A[i+1]
then swap (A[i], A[i+1])
end
Тут і далі процедура swap задає обмін значень своїх параметрів. Як бачимо, разом виконується (n-1)+(n-2)+…+1= n (n-1)/2 порівнянь. Очевидно, що найбільше можливе число елементарних дій за цим способом прямо пропорційне кількості порівнянь. Тому час сортування масиву з n
Loading...

 
 

Цікаве