Сортування й пошук: Рецептурний довідник, страница 3

Для оцінки продуктивності алгоритмів можна використати різні підходи. Самий нехитрий -просто запустити кожний алгоритм на декількох завданнях і зрівняти час виконання. Інший спосіб – оцінити час виконання. Наприклад, ми можемо затверджувати, що час пошуку є O(n) (читається так: об велике від n). Це означає, що при більших n час пошуку не сильно більше, ніж кількість елементів. Коли використають позначення O(), мають на увазі не точний час виконання, а тільки його межа зверху, причому з точністю до постійного множника. Коли говорять, наприклад, що алгоритму потрібен час порядку O(n²), мають на увазі, що час виконання завдання росте не швидше, ніж квадрат кількості елементів. Щоб відчути, що це таке, подивитеся таблицю 1.1, де наведені числа, що ілюструють швидкість росту для декількох різних функцій. Швидкість росту O(lg n) характеризує алгоритми типу двійкового пошуку. Логарифм по підставі 2, lg, збільшується на 1, коли n подвоюється. Згадаєте - кожне нове порівняння дозволяє нам шукати у вдвічі більшому списку. Саме тому говорять, що час роботи при двійковому пошуку росте як lg n.

Таблиця 0.1: Швидкість росту декількох функцій

Якщо вважати, що числа в таблиці 1.1 відповідають мікросекундам, то для завдання з 1048476 елементами алгоритму із часом роботи O(lg n) буде потрібно 20 мікросекунд, алгоритму із часом роботи O(n^1.25) – порядку 33 секунд, алгоритму із часом роботи O(n²) – більше 12 днів. У нижченаведеному тексті для кожного алгоритму наведені відповідні O-оцінки. Більше точні формулювання й докази можна знайти в літературних посиланнях, що приводять.

Отже¼

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

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

2. Сортування

Один з найпростіших способів відсортувати масив – сортування вставками. У звичайному житті ми зіштовхуємося із цим методом при грі в карти. Щоб відсортувати наявні у вас карти, ви виймаєте карту, зрушуєте карти, що залишилися, а потім вставляєте карту на потрібне місце. Процес повторюється доти, поки хоч одна карта перебуває не на місці. Як середнє, так і гірший час для цього алгоритму – O(n²). Подальшу інформацію можна одержати в книжці Батога ^[1].

Теория

На мал. 2.2 (a) ми виймаємо елемент 3. Потім елементи, розташовані вище, зрушуємо вниз – доти, поки не знайдемо місце, куди потрібно вставити 3. Це процес триває на мал. Рис. 0.1(b) для числа 1. Нарешті, на мал.2.1 (c) ми завершуємо сортування, помістивши 2 на потрібне место.

Якщо довжина нашого масиву дорівнює n, нам потрібно пройтися по  n – 1 елементам. Щораз нам може знадобитися зрушити n – 1 інших елементів. От чому цей метод вимагає таки багато часу.

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