Пошук, сортування та поняття складності у програмуванні, Детальна інформація

for k := n downto 2 do

{ k – права границя в черговому проході }

for i := 1 to k - 1 do

if A[i] > A[i+1]

then swap (A[i], A[i+1])

end

Тут і далі процедура swap задає обмін значень своїх параметрів. Як бачимо, разом виконується (n-1)+(n-2)+…+1= n\xF0D7 (n-1)/2 порівнянь. Очевидно, що найбільше можливе число елементарних дій за цим способом прямо пропорційне кількості порівнянь. Тому час сортування масиву з n елементів у такий спосіб прямо пропорційний n\xF0D7 (n-1).

Задачі

2.* Якщо при черговому виконанні циклу із заголовком for i:=1 to k-1 do процедури Bubbles1 не було жодного обміну, то масив уже відсортовано. Тому подальші проходи масивом зайві. Переробити процедуру сортування так, щоб її виконання закінчувалося за відсортованого масиву.

3. Сортування вибором здійснюється так. Проглянемо елементи масиву від першого до останнього, визначимо елемент із найменшим значенням, та обміняємо це значення з першим. Потім так само виберемо найменше значення серед A[2]...A[n] і обміняємо його зі значенням A[2], потім виберемо наступне найменше та обміняємо з A[3] тощо. Написати процедуру сортування вибором.

4. Сортування простими вставками дозволяє створити відсортований масив із значень, що читаються, наприклад, із клавіатури. Перше значення записується на перше місце, тобто присвоюється першому елементу масиву. Друге значення порівнюється з першим і, якщо перше менше, то воно "витісняється" на друге місце. Інакше нове значення йде на друге місце. Потім третє порівнюється з другим та записується або на третє місце, або витісняє значення з другого місця на третє та порівнюється з тим, що на першому місці. Наприклад, за читання послідовності значень 3, 1, 2 створюються послідовності значень у масиві <3>, <1, 3>, <1, 2, 3>.

Узагалі, після читання 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]<=v, то v записується на (i+1)-е місце. Якщо всі значення в масиві більші v, то вони зсуваються, а v записується на перше місце. Уточнити наведений алгоритм процедурою.

3. Поняття складності алгоритму та задачі

У цьому параграфі ми познайомимося з двома поняттями, які відіграють у програмуванні одну з ключових ролей. Цими поняттями є складність алгоритму та складність задачі. Почнемо з алгоритмів.

Нагадаємо, що алгоритм розв'язання масової задачі описує розв'язання будь-якого її екземпляра. Екземпляри багатьох задач можна охарактеризувати значенням деякого числового параметра. Наприклад, довжиною масиву чи кількістю чисел, які треба прочитати з клавіатури. Або натуральним числом, про яке ми хочемо дізнатися, чи просте воно. Найчастіше цим параметром є кількість скалярних значень, обробка яких задається алгоритмом. Кажуть, що екземпляр задачі має розмір N, якщо задається даними, складеними з N скалярних значень (наприклад, масивом із N елементів).

Нехай A позначає алгоритм розв'язання деякої масової задачі. Позначимо через F(A, екземпляр) кількість елементарних дій у процесі розв'язання цього екземпляра задачі за алгоритмом A, а через F(A, n) – максимум кількості елементарних дій серед усіх екземплярів розміру n.

Наприклад, якщо при бульбашковому сортуванні масив спочатку відсортований навпаки, то слідом за кожним порівнянням відбувається обмін. А це ще три присвоювання. Якщо нехтувати допоміжними операціями із змінами індексів, то

F(A, n)=4\xF0D7 n\xF0D7 (n-1)/2.

Кожному n = 1, 2, 3, … відповідає певне значення F(A, n), тобто ми маємо функціональну залежність між розмірами n та максимальними кількостями елементарних дій, виконуваних за алгоритмом A. Ця функція називається складністю алгоритму 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\xF0D7 G(n) \xF0A3 F(n) \xF0A3 C2\xF0D7 G(n).

Така залежність між функціями позначається за допомогою знака "О":

F(n) = O(G(n)).

, де C>0, C<\xF0A5 .

.

Для оцінки складності переважної більшості реальних алгоритмів достатньо логарифмічної, степеневої та показникової функцій, а також їх сум, добутків та підстановок. Усі вони монотонно зростають і задаються простими аналітичними виразами.

Приклад 1. n\xF0D7 (n-1) = O(n2), оскільки за n > 2 маємо

0.5\xF0D7 n2 < n*(n-1) < n2.

Аналогічно неважко довести, що n3 + 100\xF0D7 n2 = O(n3) = o(n3.1) = o(2n), 100\xF0D7 logn + 10000 = O(logn) = O(lgn) = o(n).