Анализ методов сортировки одномерного массива 2 (стр. 2 из 5)

Алгоритм 1 - для кожного доданка, крім a0 звести x у заданий ступінь послідовним множенням і потім домножить на коефіцієнт. Потім доданки скласти.

Обчислення i-го доданка(i=1..n) вимагає і множень. Отже, усього 1 + 2 + 3 + ... + n = n(n+1)/2 множень. Крім того, потрібно n+1 додаваннь. Усього n(n+1)/2 + n + 1= n2/2 + 3n/2 + 1 операцій.

Алгоритм 2 - винесемо x-и за дужки і перепишемо багаточлен у вигляді
Pn(x) = a0 + x(a1 + x(a2 + ... ( ai + .. x(an-1 + anx))).

Наприклад,
P3(x) = a3x3 + a2x2 + a1x1 + a0 = a0 + x(a1 + x(a2 + a3x))

Будемо обчислювати вираз зсередини. Сама внутрішня дужка вимагає 1 множення і 1 додавання. Її значення використовується для наступної дужки... І так, 1 множення і 1 додавання на кожну дужку, яких.. n-1 штука. І ще після обчислення самої зовнішньої дужки помножити на x і додати a0. Усього n множень + n додавань = 2n операцій.

Найчастіше така докладна оцінка не потрібно. Замість неї приводять лише асимптотичну швидкість зростання кількості операцій при збільшенні n.

Функція f(n) = n²/2 + 3n/2 + 1 зростає приблизно як n²/2 (відкидаємо порівняно повільно зростаючий доданок 3n/2+1). Константний множник 1/2 також забираємо й одержуємо асимптотическую оцінку для алгоритму 1, що позначається спеціальним символом O(n²) [читається як "Об велике від эн квадрат"].

Це - верхня оцінка, тобто кількість операцій(а виходить, і час роботи) росте не швидше, ніж квадрат кількості елементів. Щоб відчути, що це таке, подивитеся на таблицю, де приведені числа, що ілюструють швидкість росту для декількох різних функцій.

n	log n	n*log n	n2
1	0	0	1
16	4	64	256
256	8	2,048	65,536
4,096	12	49,152	16,777,216
65,536	16	1,048,565	4,294,967,296
1,048,576	20	20,969,520	1,099,301,922,576
16,775,616	24	402,614,784	281,421,292,179,456

Якщо вважати, що числа в таблиці відповідають мікросекундам, то для задачі з n=1048576 елементами алгоритмові з часом роботи O(log n) буде потрібно 20 мікросекунд, алгоритмові згодом O(n) - 17 хвилин, а алгоритмові з часом роботи O( n2 ) - більш 12 днів... Тепер перевага алгоритму 2 з оцінкою O(n) перед алгоритмом 1 досить переконлива.

Найкращою є оцінка O(1)... У цьому випадку час узагалі не залежить від n, тобто постійно при будь-якій кількості елементів.

Таким чином, O() - "урізана" оцінка часу роботи алгоритму, що найчастіше набагато простіше одержати, чим точну формулу для кількості операцій.

Отже, сформулюємо два правила формування оцінки O().

При оцінці за функцію береться кількість операцій, що зростає швидше всього, тобто, якщо в програмі одна функція, наприклад, множення, виконується O(n) раз, а додавання - O(n²) раз, те загальна складність програми - O(n²), тому що зрештою при збільшенні n більш швидкі ( у визначене, константне число раз ) додавання стануть виконаються настільки часто, що будуть впливати на швидкодію куди більше, ніж повільні, але рідкі множення. Символ O() показує винятково асимптотику!

При оцінці O() константи не враховуються. Нехай один алгоритм робить 2500n + 1000 операцій, а іншої - 2n+1. Обоє вони мають оцінку O(n), тому що їхній час виконання росте лінійно.

Зокрема, якщо обидва алгоритми, наприклад, O( n*log n ), те це аж ніяк не виходить, що вони однаково ефективні. Перший може бути, скажемо, у 1000 разів ефективніше. O() значить лише те, що їхній час зростає приблизно як функція n*log n.

Інший наслідок опускання константи - алгоритм згодом O(n²) може працювати значно швидше алгоритму O(n) при малих n... За рахунок того, що реальна кількість операцій першого алгоритму може бути n² + 10n + 6, а другого - 1000000n + 5. Утім, другий алгоритм рано або пізно обжене перший... n² росте куди швидше 1000000n.

Основа логарифма усередині символу O() не пишеться. Причина цього досить проста. Нехай у нас є O( log₂n). Але log₂n=log₃n/log₃2, а log₃2, як і будь-яку константу, асимптотика - символ О() не враховує. Таким чином, O( log₂n) = O( log₃n).

До будь-якої підстави ми можемо перейти аналогічно, а відповідно і писати його не має сенсу.

Математичне тлумачення символу O().

Визначення:
O(g) - безліч функцій f, для яких існують такі константи C і N, що |f(x)| <= C|g(x)| для всіх x>N.
Запис f = O(g) дослівно позначає, що f належить безлічі O(g). При цьому зворотне вираження O(g) = f не має змісту.

Зокрема, можна сказати, що f(n) = 50n належить O(n²). Тут ми маємо справу з неточною оцінкою. Зрозуміло, f(n) <= 50n² при n>1, однак більш сильним твердженням було б f(n) = O(n), тому що для C=50 і N=1 вірно f(n) <= Cn, n>N.

Інші види оцінок.

Поряд з оцінкою O(n) використовується оцінка Ώ(n) [читається як "Омега більше від эн"]. Вона позначає нижню оцінку росту функції. Наприклад, нехай кількість операцій алгоритму описує функція f(n) = Ώ(n²). Це значить, що навіть у самому вдалому випадку буде зроблено не менш порядку n² дій.
...У той час як оцінка f(n) = O(n³) гарантує, що в самому гіршому випадку дій буде порядку n³, не більше.

Також використовується оцінка Θ(n) ["Тэта від эн"], що є гібридом O() і Ώ().
Та (n²) є і верхньою і нижньої асимптотической оцінкою одночасно - завжди буде виконуватися порядку n² операцій. Оцінка Θ() існує тільки тоді, коли O() і Ώ() збігаються і дорівнює їм.

Як правило, основна увага все-таки звертається на верхню оцінку O(), тому, незважаючи на "поліпшення", алгоритм 2 залишається переважніше.

Отже, O() - асимптотическая оцінка алгоритму на гірших вхідних даних, Ώ() - на кращих вхідних даних, Θ() - скорочений запис однакових O() і Ώ().

1.3 Класифікація алгоритмів сортування

Стабільність (stability) — стійке сортування не міняє взаємного розташування рівних елементів.

Природність поводження — ефективність методу при обробці вже упорядкованих, або частково упорядкованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.

Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є

, це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів.

Інший клас алгоритмів здійснює впорядкування за час

. В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.

Ці швидкі алгоритми використовуються в реальних задачах. Проте більшість з них нестабільні. Стабільні алгоритми, що працюють за час

, потребують додаткової пам'яті.

Відомий стабільний алгоритм сортування, що не вимагає додаткової пам’яті, працює за час

Ще один клас алгоритмів використовує в своїй роботі деяку додаткову інформацію про елементи, що впорядковуються (наприклад, те що вони є різними числами в деякому діапазоні). Завдяки цьому, вони працюють за час

.

Ще одною важливою властивістю алгоритму є його сфера застосування. Тут основних типів упорядкування два:

Внутрішнє сортування оперує з масивами, що цілком поміщаються в оперативній пам'яті з довільним доступом до будь-якого осередку. Дані зазвичай упорядковуються на тому ж місці, без додаткових витрат.У сучасних архитектурах персональних комп'ютерів широко застосовується подкачка і кэширование пам'яті. Алгоритм сортування повинен добре поєднуватися із вживаними алгоритмами кешування і підкачування.

Зовнішнє сортування оперує з пристроями великого об'єму, що запам'ятовують, але з доступом не довільним, а послідовним (впорядкування файлів), тобто в даний момент ми 'бачимо' тільки один елемент, а витрати на перемотування в порівнянні з пам'яттю невиправдано великі. Це накладає деякі додаткові обмеження на алгоритм і приводить до спеціальних методів упорядкування, що звичайно використовує додатковий дисковий простір. Крім того, доступ до даних на носієві проводиться набагато повільніше, ніж операції з оперативною пам'яттю. Доступ до носія здійснюється послідовним образом: у кожен момент часу можна вважати або записати тільки елемент, що випливає за поточним. Обсяг даних не дозволяє їм розміститися в ОЗУ.

Також алгоритми класифікуються по:

1. потреби в додатковій пам'яті або її відсутності

2. потреби в знаннях про структуру даних, що виходять за рамки операції порівняння, або відсутності таких

Відомі алгоритми сортування:

За час

• сортування вибором
• сортування включенням
• сортування обміном

За час

• пірамідальне сортування
• швидке сортування
• сортування злиттям

За час

з використанням додаткової інформації про елементи

• сортування підрахунком
• сортування за розрядами
• сортування комірками

За час

• сортування злиттям модифіковане
• сортування Шелла

1.4 Постановка задачі сортування і методи її рішення.

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