і. В залежності від організації інформації впорядковані невпорядковані дані використовують різні метод
Работа добавлена на сайт samzan.net:
Пошук, сортування
та поняття складності у програмуванні
http://www.mindmeister.com/es/79132224/_
ПОШУК
Розглянемо різні методи пошуку елементу у деякому масиві.
В залежності від організації інформації, (впорядковані, невпорядковані дані) використовують різні методи пошуку.
- Послідовниий пошук
- Лінійний пошук
Описаний спосіб пошуку називаєють лінійним, простим або послідовним.
Сутність методу полягає в тому, що елементи масиву послідовно порівнюються із зразком (ключем) пошуку. Якщо має місце співпадання, то пошук закінчується. Інакше здійснюється перехід до наступного елементу. Отже, пошук припиняється або при досягненні кінця масиву, або при знаходженні заданого елемента. Даний та наступні алгоритми розглядаються для випадку, коли елементи масиву не повторюються.
|
10 |
4 |
3 |
12 |
11 |
7 |
8 |
1 |
2 |
5 |
6 |
Оскільки наявність та місцезнаходження елементу наперед невідомі, то для практичної реалізації алгоритму потрібно застосувати цикл з передумовою. Пошук елементу масиву проводять поки не знайдено відповідний елемент, або поки не дійдемо до кінця масиву.
Час пошуку за цим алгоритмом залежить від кількості n елементів масиву.
Узагальнимо присвоювання та операції над значеннями скалярних типів (порівняння, додавання, множення тощо) терміном елементарна дія. Будемо вважати, що на виконання кожної елементарної дії витрачається скінченний обмежений проміжок часу, незалежний від конкретних операндів. За такого припущення час виконання програми (підпрограми) прямо пропорційний кількості елементарних дій у процесі виконання.
Очевидно, що кількість елементарних дій прямо пропорційна кількості порівнянь A[i]<> x. В найгіршому випадку з ключем порівнюються всі елементи массиву, тоді кількість перевірок дорівнює - N. Середня кількість перевірок у разі успіху - N/2.
Звідси максимальна кількість дій та найбільший час виконання функції прямо (лінійно) пропорційні n, і найбільший час пошуку t1 є лінійною функцією від кількості елементів масиву. Лінійну залежність часу від кількості елементів, тобто довжини n, будемо позначати символом "O": t1 = O(n).
Єдина модифікація, яку можна зробити, - позбавитися перевірки номера (i <= N) за рахунок збільшення масиву на один елемент у кінці, ключ якого буде рівним x (та званий "бар'єр").
- Метод пошуку з бар’єром
Перевагою методу простого пошуку є його простота та наочність. Недоліком методу є те, що у заголовку циклу доводиться здійснювати дві перевірки: на допустимість індексу і на рівність значення. Якби ми знали, що шукане значення точно є десь у масиві, то першу перевірку на кінеці масиву можна було б не вказувати, що прискорило б пошук.
Це наштовхує на думку, що у вихідний масив потрібно тимчасово включити шукане значення. Однак, оскільки розміри масиву змінені бути не можуть, включення можна здійснити на останнє місце масиву. Тоді після завершення пошуку потрібно повернути в кінець масиву початкове значення. Для одержання результату пошуку потрібно перевірити, чи дорівнює шукане значення тому елементу масиву, на якому відбулось завершення роботи алгоритму. Навіть, якщо елемент у початковому масиві був відсутній, і зупинка була здійснена на включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку. Наведений метод називається “пошук елементу з бар'єром”. Роль бар’єрного елементу виконує включений в масив зразок пошуку.
Включення повинно здійснюватись замість останнього елементу масиву, після якого інших елементів немає.
Наприклад: Шукаємо x=7
|
10 |
4 |
3 |
12 |
11 |
7 |
8 |
1 |
2 |
5 |
6 |
an = a[n]
a[n] = x
|
10 |
4 |
3 |
12 |
11 |
7 |
8 |
1 |
2 |
5 |
7 |
Знайшли i=6
Шукаємо x=9
|
10 |
4 |
3 |
12 |
11 |
7 |
8 |
1 |
2 |
5 |
6 |
an = a[n]
a[n] = x
|
10 |
4 |
3 |
12 |
11 |
7 |
8 |
1 |
2 |
5 |
9 |
Знайшли i= n
Перевіряємо a[n] = 9 ? => ні , отже такого елемента немає в масиві
Додаткові операції по установці і зняттю бар'єра окупаються спрощенням циклу, у якому витрачається основний час при пошуку. Особливо це позначиться при великих розмірах масиву. В загальному випадку час пошуку буде меншим, ніж у попередньому випадку.
Звичайно у тому випадку, коли елементи масиву можуть повторюватись пошук не можна припиняти поки не перевірили всі елементи масиву до кінця.
|
5 |
11 |
4 |
11 |
5 |
3 |
10 |
8 |
1 |
4 |
5 |
Тоді для практичної реалізації алгоритму потрібно застосувати цикл з лічильником, а пошук проводити до кінця масиву, це дасть можливість знайти всі відповідні елементи. У такому випадку кількість перевірок дорівнює - N.
- Швидкий пошук
Якщо уявити словник на 100 тисяч слів, розташованих там без упорядкування за алфавітом, робота з таким словником буде ускладнена через незручний (повільний) пошук даних. У впорядкованому словнику слова шукати зручніше та набагато швидше. Існує багато алгоритмів пошуку по впорядкованих даних, наведемо декілька з них.
- Бінарний пошук
Якщо масив, у якому здійснюється пошук, упорядкований, то процес пошуку можна значно прискорити, застосувавши метод половинного ділення (бінарного пошуку). Сутність даного методу полягає у тому, що на кожному кроці частина масиву, в якій здійснюється пошук, зменшується удвічі. Ділення здійснюється до тих пір. Поки не буде знайдений елемент, або від масиву не залишиться жодного неопрацьованого елементу.
Припустимо, що масив впорядкований за зростанням. Поділимо його навпіл і порівняємо центральний елемент зі зразком пошуку. Якщо виконується рівність. Елемент знайдений. Якщо зразок більший за центральний елемент, то нижню частину масиву можна виключити з розгляду. Інакше виключається верхня частина. Далі процес поділу і аналізу продовжується. Таким чином, на кожному кроці потрібно зберігати індекси (номери) верхньої та нижньої межі частини масиву, що аналізується.
Такий пошук ще називають двійковим, або бінарним. Ще одна назва такого виду пошуку –дихотомічний (дихотомія – це поділ на дві половини).
Наприклад знайдемо X=10 у впорядкованому масиві:
|
2 |
4 |
5 |
7 |
8 |
9 |
10 |
11 |
14 |
Якщо вважати, що шуканий елемент знаходиться "десь усередині", спочатку перевіримо саме середній елемент: a[N div 2] = x? Якщо так, то ми знайшли, що хотіли.
|
2 |
4 |
5 |
7 |
8 |
9 |
10 |
11 |
14 |
a[5] < 10
Якщо a[N div 2] < x , то i = N div 2 є замалим і шуканий елемент знаходиться "праворуч", а якщо a[N div 2] > x , то "ліворуч", тобто на номерах 1 .. i.
|
8 |
9 |
10 |
11 |
14 |
a[7] = 10
Така перевірка фактично зменшує кількість елементів, серед яких слід шукати, вдвічі. Кожне нове ділення області пошуку ділить її навпіл. Тоді для відшукання потрібного елементу треба буде щонайбільше log2(N) перевірок. Ця пропорційність зумовлює ще одну назву описаного пошуку – логарифмічний.
Даний метод дуже ефективний, оскільки, наприклад, для масиву з 1000 елементів результат визначається навіть у гіршому випадку після 10 кроків циклу, у той час як для методів простого пошуку та пошуку з бар’єром в середньому потрібно буде 500 кроків. Однак впорядкування вихідного масиву є досить трудомісткою операцією, і вимагає часу, значно більшого, ніж проведення пошуку першими двома методами.
Таким чином, можна зробити наступні висновки: Якщо масив має невелику розмірність. То можна скористатись методом простого пошуку – постановка бар’єру істотного виграшу у швидкості не дасть. Якщо масив великий. То доцільно застосувати пошук з бар’єром. Якщо пошук проводиться багато разів в одному і тому ж масиві, то його доцільно спочатку впорядкувати, а потім застосувати бінарний пошук.
Існує кілька інших способів швидкого пошуку в масивах. Їх докладне описання є в книзі [Кнут, т.3].
- Метод стрільби
Якщо у нас немає ніякої додаткової інформації про значення ключів, крім факту впорядкування, то можна припустити, що значення елементів масиву збільшуються від a[1] до a[N-1] більш-меньш "рівномірно". Це означає, що значення x для середнього елементу a[N div 2] буде близьким до середнього арифметичного між найбільшим та найменшим значенням.
Але, якщо шукане значення x відрізняється від указанного, то є деякий сенс для перевірки брати не середній елемент, а "середньо-пропорційний", тобто такий, номер якого пропорційний значенню x (див. рис.).
Тобто ми починаєио поділ масиву не з a[N div 2]–го елемента, а з a[m] –го.
Вираз для m одержано з пропорційності відрізків на малюнку:
В "середньому" цей алгоритм має працювати швидше за двійковий пошук, але у найгіршому випадку буде працювати набагато довше.
- Метод "золотого перерізу"
Деякий ефект дає використання так званого "золотого перерізу". Це число , що має властивість:
Додатний корень
і є золотим перерізом, a
1 / = 0.61803398875 . . .
Згідно цього алгоритму відрізок L .. R слід ділити не навпіл, як у двійковому алгоритмі, а на відрізки, пропорційні та 1, у залежності від того, до якого краю ближче x. Замість оператору
m := . . . ;
у програму двійкового пошуку слід внести фрагмент
if a[R].key - x < x - a[L].key
then m := L + trunc ((R - L) * (Phi - 1.))
else m := R - trunc ((R - L) * (Phi - 1.) + 1);
а на початку програми слід задати
const
phi = 1.6180339887498948482045868; {(sqrt(5.) + 1)/2; }
Функція Trunc – округляє дробове число до цілого, відкидаючи дробову частину,
функція Round – округляє дробове число до найближчого цілого.
Індексні файли
Почнемо з прикладу:
Дані про абонента телефонної мережі включають в себе його номер, прізвище, адресу та багато іншої інформації. Шукати дані про абонента доводиться, наприклад, як за його номером, так і за прізвищем. А пошуки у відсортованому файлі значно швидші, ніж у невідсортованому. Отже, за значеннями якого з полів – номера чи прізвища – слід сортувати файл?
Відповідь на це питання дає застосування так званих індексних файлів. Розглянемо послідовність пар із рядків і чисел:
<("qw", 31), ("er", 86), ("ty", 12), ("io", 24)>.
Якщо замінити пари їх номерами (індексами) у послідовності, то упорядкування пар за алфавітним зростанням їх рядків має вигляд <2, 4, 1, 3>, тобто найменшим є "er" із пари 2, наступним – "io" із 4 тощо. Така послідовність номерів і є змістом індексного файла, відповідного цій послідовності пар за упорядкуванням рядків. Водночас, можна так само упорядкувати пари за зростанням чисел: <3, 4, 1, 2>, і це буде змістом іншого індексного файла.
Отже, значеннями елементів індексного файла є номери (або інші позначення) елементів основного файла. Перший елемент індексного файла вказує на найменший із елементів основного файла за деяким їх упорядкуванням, другий – на наступний тощо, останній – на найбільший. Якщо елементи основного файла мають багато полів, то для нього можна створити кілька різних індексних файлів.
Індексні файли дозволяють взагалі не сортувати основний файл. У випадку, коли його елементи складаються сотнями й тисячами байтів, таке сортування надто дороге. Індексні ж файли складаються з цілих чисел, і їх сортування, як правило, можна здійснити, представивши їх зміст у масиві.
Отже, використання індексних файлів дозволяє одночасно розглядати той самий файл як упорядкований за значеннями кількох різних полів його записів. Саме це дозволяє вести швидкий пошук у ньому за кількома різними ключами.
Дослідження часу роботи методів
Порівняємо швидкість методів простого пошуку і пошуку з бар’єром. Для дослідження візьмемо масив з 30000 елементів. Для визначення часу роботи методів скористаємось стандартною процедурою gettime (var hour, minute, second, sec100: word) модуля dos. Вона має наступний формат:
Gettime(h, m, s, ms);
де h – години;
m– хвилини;
s – секунди;
ms – мілісекунди.
Однак, оскільки швидкодія сучасних комп’ютерів є досить високою, а час роботи засікається лише з точністю до мілісекунд, то оцінку часу проведемо для 100 запусків процедури. Вид програми та результати її роботи наведені нижче.
Примітка. В наведеній програмі час обчислюється для виконання всієї процедури. Для більш точного визначення часу роботи вимірювання часу потрібно здійснювати в самих процедурах реалізації методів.
program poisk;
uses dos, crt;
const n=30000;
type massiv=array[1..n] of integer;
var
a:massiv;
x:integer;
i, j:integer;
h1,m1,s1,ms1:word;
h2,m2,s2,ms2:word;
t1,t2:longint;
procedure search;
begin
{лінійний пошук}
end
procedure barrier;
var b: integer;
begin
{пошук з барєром}
end.
{ ОСНОВНА ПРОГРАМА }
begin
…….
…….
writeln('Метод простого пошуку:');
gettime(h1,m1,s1,ms1);
for j:=1 to 100 do search;
getTime(h2,m2,s2,ms2);
{Перетворюємо час до мілісекунд }
t1:=(LongInt(h1)*3600+m1*60+s1)*100+ms1;
t2:=(LongInt(h2)*3600+m2*60+s2)*100+ms2;
writeln('Час пошуку t=',(t2-t1)/100/100:6:4, ' сек');
writeln;
writeln('Метод пошуку з бар’єром:');
gettime(h1,m1,s1,ms1);
for j:=1 to 100 do barrier;
getTime(h2,m2,s2,ms2);
t1:=(LongInt(h1)*3600+m1*60+s1)*100+ms1;
t2:=(LongInt(h2)*3600+m2*60+s2)*100+ms2;
writeln('Час пошуку t=',(t2-t1)/100/100:6:4, ' сек');
writeln;
end.
Результати роботи процедур:
|
Час пошуку |
|
|
Простий пошук |
Пошук з бар’єром |
|
0,0013 |
0,0007 |
|
0,0027 |
0,0015 |
Поняття складності алгоритму та задачі
Використовуючи алгоритмічні моделі ми не замислювалися над обмеженням ресурсів. Але в реальних ЕОМ і пам’ять і час обмежені. Ось чому замало знати про існування того чи іншого алгоритму – необхідно мати уявлення про необхідні ресурси, а саме:
• чи може певна програма (алгоритм) розміститися в пам’яті ЕОМ;
• чи дасть вона результат за належний час.
Дослідженням цих питань і займається розділ теорії алгоритмів – аналіз складності алгоритмів.
Складність алгоритмів – кількісна характеристика, яка визначає час, що необхідний для виконання алгоритму (часова складність), і об’єм пам’яті, необхідний для його розміщення (ємнісна складність). Часова та ємнісна складність тісно пов'язані між собою. Обидві є функціями від розміру вхідних даних. Складність розглядається, за звичай, для машинних алгоритмічних моделей (ЕОМ), оскільки в них час і пам’ять присутні у явному вигляді.
Часова характеристика (фізичний час виконання) складності алгоритму –це величина τ*t, де t – кількість дій алгоритму (елементарних команд), а τ - середній час виконання однієї операції (команди).
Кількість команд t визначається описом алгоритму в певній алгоритмічній моделі і не залежить від фізичної реалізації цієї моделі.
Середній час τ - величина фізична і залежить від швидкості обробки сигналів в елементах і вузлах ЕОМ.
Ось чому об’єктивною математичною характеристикою складності алгоритму в певній моделі є кількість команд t.
Ємкісна характеристика складності алгоритмів визначається кількістю комірок пам’яті, що використовуються в процесі його обчислення. Ця величина не може перевищувати кількість дій t, що перемножена на певну константу (кількість комірок, які використовуються при виконанні однієї команди). В свою чергу, кількість дій t може перевищувати об’єм пам’яті (за рахунок використання повторень в одних і тих же комірках). До того ж проблема пам’яті технічно долається легше, аніж проблема швидкодії, яка має фізичне обмеження – швидкість розповсюдження фізичних сигналів (300 км/с). Ось чому часова складність вважається більш суттєвою характеристикою алгоритму.
Слід зазначити, що часова складність алгоритму не є постійною величиною і залежить від розмірності задачі (об’єм пам’яті для зберігання даних) – кількість комірок для різних даних.
Отже, складність алгоритму – функція, значення якої залежить від розмірності n даних задачі. Зазвичай говорять, що час виконання алгоритму або його часова складність має порядок T(n) від вихідних даних розмірністю n.
Одиниця виміру T(n) точно не визначена, її розуміють як кількість кроків, що виконані на ідеалізованому комп’ютері.
У більшості випадків, при визначенні часової складності алгоритму Т(n), розуміють максимальний час виконання алгоритму по всім вхідним даним, так звану часову складність алгоритму Тmax(n) у найгіршому випадку.
Виконуючи аналіз алгоритмів використовують різні способи їх подання:
словесний опис, блок-схеми чи запис однією з мов програмування (машинно-орієнтованої чи високого рівня). Кожен із вказаних способів має свої переваги і оптимальнішим було б їх комплексне використання.
Взагалі є два поняття, які відіграють у програмуванні одну з ключових ролей. Це складність алгоритму та складність задачі.
Почнемо з алгоритмів.
Нагадаємо, що алгоритм розв'язання масової задачі описує розв'язання будь-якого її екземпляра. Екземпляри багатьох задач можна охарактеризувати значенням деякого числового параметра. Наприклад, довжиною масиву чи кількістю чисел, які треба прочитати з клавіатури. Найчастіше цим параметром є кількість скалярних значень, обробка яких задається алгоритмом. Кажуть, що екземпляр задачі має розмір N, якщо задається даними, складеними з N скалярних значень (наприклад, масивом із N елементів).
Нехай A позначає алгоритм розв'язання деякої масової задачі. Позначимо через F(A, екземпляр) кількість елементарних дій у процесі розв'язання цього екземпляра задачі за алгоритмом A, а через F(A, n) – максимум кількості елементарних дій серед усіх екземплярів розміру n.
Наприклад, якщо при бульбашковому сортуванні масив спочатку відсортований навпаки, то слідом за кожним порівнянням відбувається обмін. А це ще три присвоювання. Якщо нехтувати допоміжними операціями із змінами індексів, то
F(A, n)=4 n (n-1)/2.
Кожному n = 1, 2, 3, … відповідає певне значення F(A, n), тобто ми маємо функціональну залежність між розмірами n та максимальними кількостями елементарних дій, виконуваних за алгоритмом A. [http://emerecu.ukma.kiev.ua/books/PROG/ABU/abut7.htm]
Ця функція називається складністю алгоритму A. Алгоритми практично всіх реальних задач мають складність, монотонно неспадну за n.
Аналітичне задання функції F(A, n) для реальних алгоритмів, як правило, неможливе й не потрібне. Велике практичне значення має так званий порядок зростання F(A,n) за n. Він задається за допомогою іншої функції з простим аналітичним виразом, яка є оцінкою для F(A, n).
Функція G(n) є оцінкою для функції F(n), або F(n) є функцією порядку G(n), коли існують такі додатні скінченні числа C1 і C2, що за деякого m при всіх n > m
C1 G(n) F(n) C2 G(n).
Така залежність між функціями позначається за допомогою знака "О":
F(n) = O(G(n)).
Для задання порядку зростання інколи користуються іншим означенням: функція F(n) називається функцією порядку G(n) за великих n, якщо , де C>0, C< .
Функція F(n) називається функцією порядку, меншого від G(n) за великих n, і це позначається F(n)=o(G(n)), якщо .
Для оцінки складності переважної більшості реальних алгоритмів достатньо логарифмічної, степеневої та показникової функцій, а також їх сум, добутків та підстановок. Усі вони монотонно зростають і задаються простими аналітичними виразами.
Виділяють такі основні класи алгоритмів:
* логарифмічні: f(n) = O (log2n);
* лінійні: f(n) = O (n);
* поліноміальні: f(n) = O (nm); тут m - натуральне число, більше від одиниці; при m = 1 алгоритм є лінійним;
* експоненційні: f(n) = O (an); a - натуральне число, більше від одиниці.
Приклад 1:. n (n-1) = O(n2), оскільки за n > 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)
Для однієї й тієї ж задачі можуть існувати алгоритми різної складності. Часто буває і так, що більш повільний алгоритм працює завжди, а більш швидкий - лише за певних умов.
Тепер розглянемо поняття складності задачі.
Алгоритми пошуку в упорядкованому масиві свідчать, що одна й та сама задача може мати алгоритми розв'язання з різною складністю.
Неформально, під складністю задачі розуміють найменшу зі складностей алгоритмів її розв'язання. Іншими словами, задача має складність порядку G(n), якщо існує алгоритм її розв'язання зі складністю O(G(n)) і не існує алгоритмів зі складністю o(G(n)).
Наприклад, складність задачі пошуку в упорядкованому масиві визначається складністю алгоритму двійкового пошуку, тому й оцінюється функцією logn. Задача сортування масиву має складність порядку n logn. Доводити ці факти ми не будемо. (http://emerecu.ukma.kiev.ua/books/PROG/ABU/abut7.htm)
2. виховних закладів відповідно до вимог Національної доктрини розвитку освіти України
3. Этот сюжет дал возможность сатирику глубоко и всесторонне изобразить в комедии всю чиновничью Россию
4. Методы земской статистики как основа современных социологических исследований
5. настоящему ликвидировать аграрное перенаселение и разрешить агарный вопрос она не смогла тем более что пос
6. мектеп 2013ж Саба~ты~ та~ырыбы ~тілетін ме
7. Иван Андреевич Милютин
8. тематике тест в 3 классе
9. принципів права Європейського Союзу- принципи права Європейського Союзу ~ це керівні засади що концентров
10. АЮРВЕДА СЕМЬИ Матхура Мандал даса Ведический подход к зачатию и рожден
11. модульному контролю 2 Международная кадровая стратегия и трудовые отношения Корпоративная культу
12. Курсовая работа- Выбор места расположения торговых предприятий
13. 1Характеристика доброкачественных и злокачественных опухолей
14. Рынок труда в Российской Федерации
15. ТЕМА 12. СТАТИСТИЧНІ ТАБЛИЦІ І ГРАФІКИ План 12
16. на тему- Мотивационный механизм в менеджменте современных организаций
17. Оценка воздействия на окружающую среду
18. Тестовые задания, Аминоскислоты
19. Евгений Онегин обязательный для чтения и изучения в средней общеобразовательной школе.html
20. Введение 2.История законодательства и основы обеспечения сохранности документов архива 3