index-uk.php

<?php
    ob_start();
?>
        <h1 id='gentle'>Доступне введення в аналіз складності алгоритмів.</h1>
        Dionysis "dionyziz" Zindros &lt;<a href='mailto:dionyziz@gmail.com'>dionyziz@gmail.com</a>&gt;<br />
        Переклад: <a href="https://yuga.ego.team" target="_blank">Y. E. T.</a>

        <?= $translations ?>

        <h2 id='intro'>Вступ</h2>
        <p>Багато хто з сучасних програмістів &mdash; тих що створюють круті та надзвичайно корисні програми, які ми бачимо в Інтернеті або використовуємо щодня &mdash; не мають теоретичних знань з інформатики. Все одне такі програмісти є відмінними фахівцями, і ми вдячні їм за те, що вони роблять.</p>

	<p>Однак теоретичні знання мають прикладне значення і можуть бути використані для розв&apos;язання практичних проблем. Ця стаття призначена для програмістів, які знають своє мистецтво, але не мають теоретичних знань. Я познайомлю вас з одним із прагматичних інструментів інформатики: аналіз складності алгоритмів. Я працював як в академічних колах, так і в області прикладної розробки програмного забезпечення, і виявив, що це дійсно корисний інструмент. Тому я сподіваюся, що прочитавши цю статтю, і ви зможете застосувати його для поліпшення коду. Ви зрозумієте загальноприйняті терміни в інформатиці, такі як &laquo;О&raquo; велике, асимптотична поведінка й аналіз найгіршого випадку.</p>

        <p>Цей текст також призначений для учнів середніх і старших класів, які беруть участь у <a href='https://uk.wikipedia.org/wiki/Міжнародна_олімпіада_з_інформатики'>Міжнародній олімпіаді з інформатики</a> або інших подібних конкурсах. Таким чином, ця стаття не вимагає від вас глибоких математичних знань і надає необхідний теоретичний матеріал для подальшого вивчення алгоритмів. Я сам брав участь у таких конкурсах, а тому наполегливо рекомендую уважно прочитати весь вступний матеріал і спробувати повністю його зрозуміти, оскільки це необхідно для подальшого вивчення алгоритмів і більш складних методів їх аналізу.</p>

	<p>Цей текст буде корисним для програмістів практиків, яким не вистачає теоретичних знань (деякі з найбільш надихаючих інженерів програмного забезпечення не мають вищої освіти). Однак майте на увазі, що стаття також написана для учнів, тому час від часу вона може нагадувати підручник. Деякі теми можуть бути занадто простими для вас; наприклад, якщо ви вже зустрічалися з ними. В такому випадку можете перейти до наступної теми. Наступні розділи більше заглиблюються в розглянуті питання і набувають теоретичне забарвлення, оскільки студенти, які беруть участь у змаганнях, потребують цих знань. Однак усі теми, які тут обговорюються, корисно знати; вони доступні для розуміння й тому, швидше за все, гідні вашого часу.</p>

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

        <p>Велика кількість програмістів та учнів вважає, що аналіз складності алгоритмів важкий для розуміння. Вони бояться його або навіть повністю його уникають. Насправді &laquo;O&raquo; велике й аналіз складності алгоритмів не такі важкі для розуміння, як це може здаватися. Аналіз складності алгоритмів &mdash; це всього лише спосіб оцінити швидкість роботи програми або алгоритму, так що це дуже практичний інструмент. Почнімо з невеликої мотивації.</p>

        <div class='sidefigure'>
            <img src='images/halflife2.jpg' alt='Знімок екрану з персонажем, керованим штучним інтелектом гри Half-life 2.' />
            <label><strong>Ілюстрація 1</strong>: Штучний інтелект у відеоіграх використовує алгоритми для переміщення персонажів з урахуванням обходу перешкод.</label>
        </div>

        <h2 id='motivation'>Мотивація</h2>
	
        <p>Ми вже знаємо про існування інструментів, що вимірюють швидкість роботи коду. Ці програми називаються <em>профайлерами</em> (англ. profilers). Профайлери вимірюють тривалість роботи коду в мілісекундах і допомагають виявляти <em>вузькі місця</em> (англ. bottleneck) в роботі коду, для подальшої його оптимізації. При всій корисності таких інструментів, профайлери не мають відношення до складності алгоритмів. Аналіз складності алгоритмів був розроблений для порівняння алгоритмів на рівні їхніх ідей, ігноруючи несуттєві деталі: використані мова програмування, обладнання, набір команд центрального процесора. Ми хочемо порівняти сутність алгоритмів: ідеї, яким чином має бути здійснене обчислення. Підрахунок мілісекунд не допоможе нам впоратися з таким завданням. Цілком ймовірно, що поганий алгоритм, написаний мовою низького рівня &mdash; наприклад мовою <a href='https://uk.wikipedia.org/wiki/Мова_асемблера'>асемблера</a> &mdash; відпрацює набагато швидше хорошого алгоритму, написаного високорівневою мовою програмування &mdash; наприклад мовою <a href='https://www.python.org/'>Python</a> або <a href='https://www.ruby-lang.org'>Ruby</a>. Отже, настав час дати визначення поняттю &laquo;кращий алгоритм&raquo;.</p>

        <p>Оскільки алгоритми &mdash; це програми, зайняті обчисленнями (на відміну від інших завдань, які виконуються комп'ютерами: мережевих, введення та виведення даних користувачем), аналіз складності дозволяє нам виміряти швидкість роботи програми. Приклади суто <em>обчислювальних</em> операцій охоплюють операції з числами, представленими у <a href='https://uk.wikipedia.org/wiki/Число_з_рухомою_комою'>формі з рухомою комою</a> (такі як додавання й множення); пошук по <a href="https://uk.wikipedia.org/wiki/База_даних">базі даних в оперативній пам&apos;яті</a> (англ. in-memory database); знаходження найкоротшого шляху для персонажа, керованого штучним інтелектом (<strong>Ілюстрація 1</strong>); або ж пошук у тексті з використанням <a href='https://uk.wikipedia.org/wiki/Регулярний_вираз'>регулярних виразів</a>. Очевидно, що обчислювальні завдання зустрічаються повсюдно в комп'ютерних програмах.</p>

	<p>Аналіз складності також дозволяє описати, як алгоритм поводиться при збільшенні розміру вхідних даних. Як поведе себе алгоритм отримавши іншу кількість вхідних даних? Якщо наш алгоритм відпрацьовує за 1 секунду, отримавши 1000 одиниць вхідних даних, то як він поведе себе, отримавши в два рази більше даних? Чи буде він працювати з тією ж швидкістю або в два рази повільніше, або в чотири рази повільніше? Аналіз складності дозволяє передбачати поведінку алгоритму, що важливо для прикладного програмування. Припустимо, ми написали алгоритм для вебдодатку так, що він гарно працює з даними 1000 користувачів, і виміряли наскільки швидко він справляється зі своїм завданням. Тоді аналіз складності алгоритму дозволяє нам оцінити швидкість алгоритму при роботі з даними 2000 користувачів. Для змагань з інформатики, аналіз складності дає розуміння, скільки часу знадобиться нашому коду, щоб обробити найбільші тестові дані, які використовуються для перевірки правильності роботи нашої програми. Таким чином, якщо ми виміряємо швидкість роботи програми з малою кількістю вхідних даних, тоді ми можемо оцінити, яка буде швидкість її роботи з великою кількістю даних. Почнемо з простого прикладу: знаходження найбільшого елементу в масиві даних.</p>

        <h2>Підрахунок інструкцій</h2>
	
	<p>У цій статті приклади коду будуть написані на різних мовах програмування. Не засмучуйтесь, якщо ви не знайомі з будь-якими з них. Усі приклади будуть простими, без використання езотеричних можливостей мов, так що людина, знайома з програмуванням, зможе зрозуміти всі приклади без проблем. Якщо ви учень, який бере участь у змаганнях, ви найімовірніше знайомі з <a href='http://cppstudio.com/uk/'>C ++</a>, так що приклади й для вас повинні бути зрозумілими. Учням я рекомендую попрактикуватися з прикладами, написавши їх на C ++.</p>

        <p>Ми можемо знайти найбільший елемент масиву використовуючи показаний нижче фрагмент <a href="https://developer.mozilla.org/uk/docs/Web/JavaScript">Javascript</a>  коду. Припустимо нам дано масив даних <var>A</var> з розміром <var>n</var> >= 1. Тоді:</p>

        <pre name='code' class='brush: js; gutter: false; toolbar: false'>
            var M = A[ 0 ];

            for ( var i = 0; i &lt; n; ++i ) {
                if ( A[ i ] &gt;= M ) {
                    M = A[ i ];
                }
            }
        </pre>
	
	<p>Спочатку ми підрахуємо кількість базових команд у цьому фрагменті коду. Ми зробимо такий підрахунок тільки один раз. Необхідність у ньому пропаде у міру розбору теорії, так що наберіться трохи терпіння. Під час аналізу цього фрагменту коду, ми хочемо розбити його на прості команди: ті, які можуть бути виконані процесором безпосередньо (або близько до цього). Припустимо, що наш процесор може виконувати такі операції як одну команду:</p>

        <ul>
            <li>Присвоїти значення змінної.</li>
            <li>Знайти значення заданого елемента в масиві.</li>
            <li>Порівняти два значення.</li>
            <li>Збільшити значення на одиницю (інкремент).</li>
            <li>Провести базові арифметичні дії (додавання, віднімання).</li>
        </ul>

        <p>Ми припустимо, що <a href="https://uk.wikipedia.org/wiki/Умовний_перехід">розгалуження</a> (вибір між частинами коду в тілі <code>if</code> або <code>else</code>) відбувається миттєво, і не будемо підраховувати ці команди. Розглянемо перший рядок коду, показаного вище:</p>

        <pre class='brush: jscript; gutter: false; toolbar: false;'>
            var M = A[ 0 ];
        </pre>

        <p>Цей рядок містить дві команди: одна знаходить елемент масиву  <var>A[ 0 ]</var>, інша привласнює знайдену величину змінній <var>M</var>. Алгоритм завжди виконує ці дві команди, незалежно від значення <var>n</var>. Цикл <code>for</code> теж виконується завжди та дає нам ще дві команди: присвоювання і порівняння.</p>

        <pre class='brush: jscript; gutter: false; toolbar: false;'>
            i = 0;
            i &lt; n;
        </pre>

        <p>Вони відпрацюють до першої ітерації циклу <code>for</code>. Після кожної ітерації циклу <code>for</code>, відпрацюють ще дві команди: інкременту та порівняння (для перевірки, чи залишаємося ми в циклі):</p>

        <pre class='brush: jscript; gutter: false; toolbar: false;'>
            ++i;
            i &lt; n;
        </pre>
	
        <p>Ми ігноруємо тіло циклу, тому кількість команд, що виконуються цим алгоритмом, дорівнює 4 + 2n. А саме, 4 команди на початку циклу <code>for</code> і 2 команди в завершенні кожної ітерації (всього здійснюється <var>n</var> ітерацій). Тепер ми можемо визначити математичну функцію f( n ), яка співвідносить n з кількістю команд, які виконуються алгоритмом. При порожньому тілі циклу <code>for</code>, f( n ) = 4 + 2n.</p>

        <h2 id='worst'>Аналіз найгіршого випадку</h2>

        <p>Наразі подивимося на тіло циклу <code>for</code>. Тут завжди здійснюються пошук у масиві й операція порівняння:</p>

        <pre class='brush: jscript; gutter: false; toolbar: false;'>
            if ( A[ i ] &gt;= M ) { ...
        </pre>

        <p>Тобто в тілі циклу виконуються дві команди. Однак виконання або невиконання команд у тілі <code>if</code> залежить від значень елементів масиву. Якщо <code>A[ i ] &gt;= M</code>, тоді відпрацюють ще дві команди: пошуку в масиві та присвоювання:</p>
	
        <pre class='brush: jscript; gutter: false; toolbar: false;'>
            M = A[ i ]
        </pre>
	
        <p>Але тепер ми більше не можемо легко визначити f( n ), тому що кількість команд залежить не тільки від <var>n</var>, але й від значень, що вводяться. Наприклад, при <code>A = [ 1, 2, 3, 4 ]</code>, алгоритму знадобиться виконати більше команд, ніж при <code>A = [ 4, 3, 2, 1 ]</code>. При аналізі алгоритмів часто розглядається найгірший сценарій. Які вхідні дані самі несприятливі для нашого алгоритму? В якому випадку алгоритму знадобиться виконати максимальну кількість операцій? Для розглянутого прикладу найгірший варіант &mdash; це отримати масив, відсортований за зростанням, наприклад: <code>A = [ 1, 2, 3, 4 ]</code>. У такому випадку з кожною новою ітерацією значення i-го елементу масиву буде присвоєно <var>M</var>, а це є максимальна кількість команд. Для таких випадків у теоретиків є чудна назва: <em>аналіз найгіршого випадку</em>; але це всього лише розгляд самого невдалого варіанту. Отже, у найгіршому разі в тілі циклу <code>for</code> відпрацює 4 команди. Разом, f( n ) = 4 + 2n + 4n = 6n + 4. Функція f при заданій проблемі з розміром n дає нам кількість команд, виконуваних у найгіршому випадку.</p>

        <h2 id='asymptotic'>Асимптотична поведінка</h2>
	
        <p>Отримана вище функція дає нам досить чітке уявлення про швидкість роботи алгоритму. Однак, як я й обіцяв, нам не знадобиться кожного разу займатися трудомістким підрахунком кількості команд у програмі. До того ж кількість реальних команд, які виконуються процесором, залежить від компілятора нашої мови програмування та від типу самого процесора. Як ми вже говорили, ми ігноруємо цю різницю. Зараз ми пропустимо нашу функцію &laquo;f&raquo; крізь &laquo;фільтр&raquo;, який допоможе нам позбутися несуттєвих деталей, ігнорованих під час аналізу.</p>

        <p>Функція <code>f( n ) = 6n + 4</code> складається з двох членів: 6n і 4. При аналізі складності нас цікавить, що відбувається з функцією підрахунку команд при збільшенні кількості вхідних даних <var>n</var>. Цей підхід добре відповідає аналізу поведінки у найгіршому випадку: нам цікаво дізнатися, як алгоритм поведе себе в &laquo;поганих&raquo; умовах (при необхідності обробити важку задачу). Зауважте, що це дуже зручно для порівняння алгоритмів між собою. Якщо один алгоритм &laquo;перемагає&raquo; в іншого при великій кількості вхідних даних, тоді найбільш імовірно, що швидкіший алгоритм залишиться таким і при меншій кількості вхідних даних. <strong>Тому, ми знехтуємо членами функції, які ростуть повільно, і залишимо ті, які ростуть дуже швидко при збільшенні n</strong>. Явно, що 4 залишиться рівним 4 при будь-якому значенні <var>n</var>. При цьому 6n постійно зростатиме зі збільшенням значення <var>n</var>, так що саме 6n гратиме все більшого значення зі збільшенням вхідних даних. Отже, ми можемо знехтувати значенням 4 і записати нашу функцію в такому вигляді: <code>f( n ) = 6n</code>.</p>

        <p>І це розумний підхід, адже 4 &mdash; всього лише &laquo;константа ініціалізації&raquo;. Різні мови програмування потребують різну кількість часу для ініціалізації. Наприклад, мові Java потрібна значна кількість часу для запуску <a href="https://uk.wikipedia.org/wiki/Віртуальна_машина_Java">віртуальної машини</a>. Через то, що ми ігноруємо відмінності між мовами програмування, буде правильно знехтувати й константою 4.</p>

        <p>Ще один елемент, яким можна знехтувати &mdash; це постійний множник 6. Таким чином, нашу функцію можна записати в такому вигляді: <code>f( n) = n</code>. Як бачите, ми дуже сильно спростили процедуру підрахунку команд. І це знову виглядає як розумний підхід, беручи до уваги, що різні мови програмування компілюються по-різному. Наприклад мова C, виконуючи інструкцію <code>A[ i ]</code>, не перевіряє, чи знаходиться значення &laquo;<var>i</var>&raquo; в діапазоні розміру масиву. Разом з тим <a href='https://uk.wikipedia.org/wiki/Pascal'>Паскаль</a> робить таку перевірку. Іншими словами, наступний фрагмент коду на мові Паскаль:</p>

        <pre class='brush: delphi; gutter: false; toolbar: false;'>
            M := A[ i ]
        </pre>

        <p>є еквівалентним такому фрагменту на мові C:</p>

        <pre class='brush: c; gutter: false; toolbar: false;'>
            if ( i &gt;= 0 &amp;&amp; i &lt; n ) {
                M = A[ i ];
            }
        </pre>

	<p>Так що під час підрахунку команд прийнятно очікувати різні множники у випадку різних мов програмування. В нашому прикладі для мови Паскаль використовується найпримітивніший компілятор, без будь-якої оптимізації. У такому випадку Паскаль потребує 3 команди для кожного запиту до масиву даних; замість лише 1 команди, що виконується мовою C. Опускаючи відповідний множник, ми чинимо згідно до вже прийнятого нами підходу ігнорування різниці між мовами програмування й аналізу самої сутності алгоритмів.</p>

        <p>Описаний вище фільтр &laquo;знехтування множниками та константами&raquo; має назву: <em>асимптотична поведінка</em>. Так, асимптотична поведінка функції <code>f( n ) = 2n + 8</code> описується функцією <code>f( n ) = n</code>. Говорячи математичною мовою, нам цікава межа функції f при <var>n</var>, що прагне до нескінченності. (Якщо вам не зрозумілий сенс цієї фрази, не хвилюйтеся: досить, що ви ознайомилися з цим формулюванням. Примітка: при строгому математичному підході ми не змогли б знехтувати константами; але для задач у сфері інформатики ми це робимо з причин, описаних вище). А тепер опрацюємо пару прикладів, щоб звикнути до вже описаних концепцій.</p>

        <div class='right sidefigure'>
            <img src='images/cubic-vs-linear.png' alt='Кубічна функція має більші значення, ніж лінійна функція, після n = 45' />
            <label><strong>Ілюстрація 2</strong>: Після n = 45, значення функції n<sup>3</sup> (синій графік) назавжди стають більшими, ніж значення функції 1999n (червоний графік).</label>
        </div>

        <p>Знайдемо асимптотичну поведінку наступних функцій:</p>

        <ol>
            <li><p>f( n ) = 5n + 12 дає f( n ) = n.</p>
                <p>Згідно до вже викладеного ходу думки.</p></li>

            <li><p>f( n ) = 109 дає f( n ) = 1.</p>
                <p>Ми нехтуємо множником 109 * 1, але повинні залишити 1 для позначення, що функція має не нульове значення.</p></li>

            <li><p>f( n ) = n<sup>2</sup> + 3n + 112 дає f( n ) = n<sup>2</sup></p>
                <p>n<sup>2</sup> зростає швидше, ніж 3n, при достатньо великому значенні <var>n</var>.</p></li>

            <li><p>f( n ) = n<sup>3</sup> + 1999n + 1337 дає f( n ) = n<sup>3</sup></p>
                <p>Множник 1999 досить великий, але ми все ж можемо знайти досить велике значення <var>n</var>, таке, що n<sup>3</sup> буде більше, ніж 1999n. А оскільки ми зацікавлені в поведінці при дуже великих значеннях <var>n</var>, то ми залишаємо тільки n<sup>3</sup> (дивіться <strong>Ілюстрацію 2</strong>).</p></li>

            <li><p>f( n ) = n + <img alt='sqrt( n )' src='images/sqrtn.png' /> дає f( n ) = n</p>
                <p>Через те, що n зростає швидше, ніж <img alt='sqrt( n )' src='images/sqrtn.png' /> у міру збільшення <var>n</var>.</p></li>
        </ol>

        <p>Спробуйте знайти асимптотичну поведінку наступних функцій самостійно:</p>
        <div class='exercise'>
            <h3>Вправа 1</h3>
            <ol>
                <li>f( n ) = n<sup>6</sup> + 3n</li>
                <li>f( n ) = 2<sup>n</sup> + 12</li>
                <li>f( n ) = 3<sup>n</sup> + 2<sup>n</sup></li>
                <li>f( n ) = n<sup>n</sup> + n</li>
            </ol>
            <p>(Запишіть ваші результати; відповіді дані нижче.)</p>

            <p>Якщо у вас виникли проблеми з будь-якої з функцій, підставте в цю функцію велике значення <var>n</var> і порівняйте, який з членів стає більшим. Досить-таки просто, еге ж?</p>
        </div>

        <h2 id='complexity'>Складність</h2>

        <p>Отже, через те що ми можемо знехтувати всіма декоративними константами, досить легко визначити асимптотичну поведінку функції підрахунку команд. Дійсно, асимптотичною поведінкою будь-якої програми без циклів буде f (n) = 1, бо кількість команд, які виконуються такою програмою, завжди дорівнюється якійсь константі (це не стосується випадку рекурсії, розглянутого нижче). Асимптотична поведінка будь-якої програми з одним циклом, що проходить від 1 до <var>n</var>, буде f( n ) = n, бо така програма буде викликати якусь постійну кількість команд до початку циклу, після завершення циклу та всередині циклу (команди всередині циклу завжди будуть викликатися <var>n</var> разів).</p>

        <p>Такий підхід мусить бути значно легшим, ніж трудомісткий підрахунок усіх команд програми. Через це розглянемо декілька прикладів, щоб звикнути до нього. Наступна програма, написана на мові <a href='https://www.php.net/manual/en/getting-started.php'>PHP</a>, перевіряє, чи знаходиться дане значення у масиві <var>A</var> з розміром <var>n</var>:</p>

        <pre class='brush: php; gutter: false; toolbar: false;'>
            &lt;?php
                $exists = false;
                for ( $i = 0; $i &lt; n; ++$i ) {
                    if ( $A[ $i ] == $value ) {
                        $exists = true;
                        break;
                    }
                }
            ?&gt;
        </pre>

        <p>Такий метод пошуку значення в масиві даних називається <em>лінійним пошуком</em>. Це влучне ім&apos;я, бо асимптотичну поведінку цієї програми описує функція f( n ) = n (ми дамо точне визначення &laquo;лінійності&raquo; в наступному розділі). Зверніть увагу на інструкцію &laquo;break&raquo;, яка може викликати раніше завершення роботи програми (можливо, відразу ж на першому кроці циклу). Згадайте, що нас цікавить тільки найгірший сценарій. Для даної програми &mdash; це відсутність шуканого елемента в масиві <var>A</var>. Так що ми все ще маємо f( n ) = n.</p>

        <div class='exercise'>
            <h3>Вправа 2</h3>

            <p>Використовуючи дану вище програму на мові PHP, підрахуйте кількість команд, що викликаються цією програмою в найгіршому випадку, і виведіть функцію підрахунку команд f (n), як ми це вже робили на прикладі Javascript програми. Потім перевірте, що асимптотично ми отримуємо складність <code>f( n ) = n</code>.</p>
        </div>

	<p>Погляньте на програму написану на мові Python. Ця програма складає значення двох елементів масиву та привласнює результат складання новій змінній:</p>

        <pre class='brush: python; gutter: false; toolbar: false;'>
            v = a[ 0 ] + a[ 1 ]
        </pre>

        <p>Ця програма містить постійну кількість команд, тож f( n ) = 1.</p>

        <p>Наступна програма на мові C ++ перевіряє, чи містить вектор (чуднуватий масив) <var>A</var> з розміром <var>n</var> два однакових значення:</p>

        <pre class='brush: cpp; gutter: false; toolbar: false;'>
            bool duplicate = false;
            for ( int i = 0; i &lt; n; ++i ) {
                for ( int j = 0; j &lt; n; ++j ) {
                    if ( i != j &amp;&amp; A[ i ] == A[ j ] ) {
                        duplicate = true;
                        break;
                    }
                }
                if ( duplicate ) {
                    break;
                }
            }
        </pre>

        <p>Ця програма містить в собі вкладені цикли. В такому випадку асимптотична поведінка описується функцією f( n ) = n<sup>2</sup>.</p>

        <div class='highlight'>
            <p class='thumb'><strong>Підказка</strong>: Прості програми можуть бути проаналізовані шляхом підрахунку циклів. Одиничний цикл із n кроками призводить до складності f (n) = n. Додатковий вкладений цикл призводить до складності f( n ) = n<sup>2</sup>. Цикл всередині циклу всередині циклу дає складність f( n ) = n<sup>3</sup>.</p>
        </div>

        <p>Якщо програма викликає функцію в тілі циклу, та якщо нам відома кількість команд, виконуваних цією функцією, тоді нескладно підрахувати кількість команд, які виконуються всією програмою. Дійсно, погляньте на такий приклад на мові C:</p>

        <pre class='brush: c; gutter: false; toolbar: false;'>
            int i;
            for ( i = 0; i &lt; n; ++i ) {
                f( n );
            }
        </pre>

        <p>Якщо нам відомо, що <code>f( n )</code> виконує <var>n</var> команд, то нам відомо, що кількість команд, які виконуються всією програмою, асимптотично дорівнює n<sup>2</sup>, бо функція <code>f( n )</code> буде викликана точно <var>n</var> разів.</p>

        <div class='highlight'>
            <p class='thumb'><strong>Підказка</strong>: Якщо нам дана послідовність циклів for, то найповільніший з них визначає асимптотичну поведінку всієї програми. Двоє вкладених циклів, за якими слідує одиничний цикл, асимптотично дорівнюються просто двом вкладеним циклам, тому що вкладені цикли <em>домінують</em> над одиничним.</p>
        </div>

        <p>Тепер перейдемо до незвичного способу запису, що використовується теоретиками. Коли ми виводимо асимптотичну поведінку, ми можемо сказати, що наша програма &mdash; це Θ( f( n ) ). Наприклад, програми вище &mdash; це, відповідно, Θ( 1 ), Θ( n<sup>2</sup> ) та Θ( n<sup>2</sup> ). Θ( n ) вимовляється як &laquo;тета від ен&raquo;. Іноді ми говоримо, що f( n ), початкова функція підрахунку команд, яка містить константи, &mdash; це Θ( щось ). Наприклад, можна сказати, що функція f( n ) = 2n &mdash; це Θ( n ). Ще один варіант запису: 2n ∈ Θ( n ), вимовляється як "два ен це тета від ен". Не треба ніяковіти, адже цей запис лише говорить: ми підрахували кількість команд, які виконуються програмою, і вона дорівнює 2n; тобто асимптотичну поведінку алгоритму можна описати як n (опустивши константу 2). Наступні математичні вирази використовують новий спосіб запису:</p>
        <ol>
            <li>n<sup>6</sup> + 3n ∈ Θ( n<sup>6</sup> )</li>
            <li>2<sup>n</sup> + 12 ∈ Θ( 2<sup>n</sup> )</li>
            <li>3<sup>n</sup> + 2<sup>n</sup> ∈ Θ( 3<sup>n</sup> )</li>
            <li>n<sup>n</sup> + n ∈ Θ( n<sup>n</sup> )</li>
        </ol>

        <p>До речі, це і є відповіді до вправи 1.</p>

        <p><strong>Ми називаємо цю функцію &mdash; я маю на увазі ту функцію, котру ми маємо Θ( тут ) &mdash; <em>часовою складністю</em> або просто <em>складністю</em> алгоритму.</strong> Так, алгоритм із Θ( n ) має складність n. У нас також є спеціальні назви для Θ( 1 ), Θ( n ), Θ( n<sup>2</sup> ) та Θ( log( n ) ), бо це розповсюдженні класи складності. Алгоритм із Θ( 1 ) має назву <em>алгоритм сталого часу</em>, Θ( n ) &mdash; <em>лінійний алгоритм</em>, Θ( n<sup>2</sup> ) &mdash; <em>квадратичний</em>, Θ( log( n ) ) &mdash; <em>логарифмічний</em> (не турбуйтеся, якщо ви не знайомі з останнім терміном, логарифми будуть розглянуті трохи нижче).</p>

        <div class='highlight'>
            <p class='thumb'><strong>Підказка</strong>: Чим більше Θ, тим повільніше працює програма.</p>
        </div>

        <div class='right sidefigure'>
            <img src='images/hidden-surface.jpg' alt='Приклад прихованої поверхні в відеогрі' />
            <label><strong>Ілюстрація 3</strong>: Гравець, розташований в зоні, зазначеній жовтою точкою, не бачитиме затемненої зони. Одним зі способів визначення зони видимості є розбиття світу на маленькі фрагменти та подальше сортування цих фрагментів.</label>
        </div>

        <h2 id='big-o'>&laquo;O&raquo; велике</h2>

        <p>Насправді іноді нелегко визначити поведінку алгоритму, використовуючи даний вище підхід. Особливо це стосується більш складних прикладів. Хай там як, завжди можливо оцінити діапазон поведінки алгоритму. Це полегшує нам життя, оскільки звільняє від необхідності визначати точну швидкість роботи алгоритму. Все, що нам необхідно зробити &mdash; це визначити межі поведінки алгоритму. Цей підхід роз'яснюється в наступному прикладі.</p>

        <p>Для навчання алгоритмам зазвичай використовується задача <em>сортування</em>. У цьому завданні дається масив <var>A</var> з розміром <var>n</var> (звучить знайомо?), і нас просять написати програму, яка впорядковує елементи масиву. Це цікаве завдання: воно має практичне застосування в реальних системах. Наприклад, менеджер файлів повинен впорядкувати файли за назвою, для спрощення навігації користувача. Або інший приклад: відеогрі необхідно впорядкувати 3D об&apos;єкти світу на підставі їх розташування щодо гравця, для визначення, які з об'єктів видимі, а які ні (<a href='https://en.wikipedia.org/wiki/Hidden_surface_determination'>розрахунок області видимості</a>, дивіться <strong>Ілюстрацію 3</strong>). Найближчі до гравця об&apos;єкти будуть видимі, а більш віддалені можуть бути приховані об&apos;єктами між ними. Сортування стає ще цікавішим через наявність різних за ефективністю алгоритмів сортування. І, нарешті, це досить доступне для пояснення та розуміння завдання. Так що і ми зараз напишемо код сортування масиву.</p>

        <p>Далі показаний неефективний спосіб реалізації сортування масиву, написаний на мові Ruby. (Звичайно ж, Ruby надає вбудовані функції для сортування масиву, які й слід використовувати в більшості випадків. Вбудовані функції працюють швидше, ніж показана нижче програма, запропонована суто для ілюстрації).</p>

        <div class='leftofimage'>
            <pre class='brush: ruby; gutter: false; toolbar: false;'>
                b = []
                n.times do
                    m = a[ 0 ]
                    mi = 0
                    a.each_with_index do |element, i|
                        if element &lt; m
                            m = element
                            mi = i
                        end
                    end
                    a.delete_at( mi )
                    b &lt;&lt; m
                end
            </pre>
        </div>

        <p>Такий метод називається <a href='https://uk.wikipedia.org/wiki/Сортування_вибором'>сортування вибором</a> (англ. selection sort). Сортування вибором знаходить найменше значення масиву (ми позначили масив як <var>a</var>, мінімальне значення <var>m</var>, індекс цього значення <var>mi</var>), додає знайдене значення до кінця масиву <var>b</var> і видаляє це значення з заданого масиву <var>a</var>. Потім алгоритм знову знаходить мінімальне значення серед решти елементів масиву <var>a</var>, додає його до кінця масиву <var>b</var> (тепер масив <var>b</var> містить два відсортованих елемента) та видаляє з масиву <var>a</var>. Перелічені кроки повторюються, доки початковий масив не стане порожнім, а всі його елементи виявляться перенесеними в новий, відсортований, масив. Цей приклад містить вкладені цикли. Зовнішній цикл відпрацьовує <var>n</var> раз, а внутрішній масив відпрацьовує один раз для кожного елемента масиву <var>a</var>. Спочатку масив <var>a</var> містить <var>n</var> елементів, проте ми видаляємо з нього один елемент на кожному кроці зовнішнього циклу. Так що внутрішній цикл відпрацьовує <var>n</var> разів під час першого кроку зовнішнього циклу, потім <code>n - 1</code> разів, потім <code>n - 2</code> разів і так далі, до останнього кроку зовнішнього циклу, на якому внутрішній цикл відпрацює лише один раз.</p>

        <p>Оцінити складність цієї програми трохи важче, позаяк нам треба підрахувати суму 1 + 2 + ... + (n - 1) + n. Але ми точно можемо знайти &laquo;верхню межу&raquo; для цієї програми. Адже ми можемо змінити нашу програму (ви можете виконати цю операцію в умі, без написання коду) таким чином, щоб вона стала <strong>гіршою</strong>, ніж вона є насправді, а потім знайти складність такої виведеної програми. Якщо ми знайдемо складність виведеної програми, то складність початкової програми буде такою ж або навіть меншою. Тобто, якщо виявиться, що виведена програма досить ефективна (ця ефективність за визначенням гірша, ніж у початкової програми), то ми зможемо зробити висновок, що початкова програма теж має гарну ефективність. Принаймні не меншу (або навіть більшу), ніж у виведеної &mdash; погіршеної  &mdash; програми.</p>

        <p>А зараз поміркуємо про засіб редагування програми з прикладу таким чином, щоб спростити оцінку її складності. При цьому майте на увазі, що ми можемо змінювати програму лише в бік погіршення, тобто робити так, щоб вона виконувала ще більше команд (аби оцінка складності правильно співвідносилася з початкової програмою). Очевидно, що ми можемо змінити кількість кроків, які виконуються внутрішнім циклом програми так, щоб їх завжди було точно <var>n</var>, замість зменшення кількості кроків. Деякі з цих повторень будуть марними для сортування, але спростять нам аналіз складності алгоритму. Якщо ми зробимо цю просту зміну, тоді новий, тільки що сконструйований, алгоритм буде оцінюватися як Θ( n<sup>2</sup> ), тому що він буде складатися з двох вкладених циклів, кожен з яких повторюється <var>n</var> разів. У такій ситуації ми говоримо, що початковий алгоритм має складність O( n<sup>2</sup> ). O( n<sup>2</sup> ) вимовляється як &laquo;велике о від ен у квадраті&raquo;. Це означає, що наша програма асимптотично не гірша, ніж n<sup>2</sup> (вона може навіть бути кращою або дорівнювати n<sup>2</sup>). Між іншим, якщо наша програма насправді має складність Θ( n<sup>2</sup> ), то це також відповідає O( n<sup>2</sup> ). Щоб допомогти вам це зрозуміти, уявіть, як ви змінюєте початкову програму зовсім трішечки, але все ж погіршує її продуктивність, наприклад додавши несуттєву команду на початку програми. Таким чином ви зміните функцію підрахунку команд на константу, ігноровану при визначенні асимптотичної поведінки. Звідси випливає, що програма Θ( n<sup>2</sup> ) також є O( n<sup>2</sup> ).</p>

        <p>А ось програма зі складністю O( n<sup>2</sup> ) може не мати Θ( n<sup>2</sup> ). Наприклад, будь&dash;яка програма з Θ( n ) &mdash; це також O( n<sup>2</sup> ), на додачу до O( n ). Уявімо, що програма Θ( n ) &mdash; це простий цикл <code>for</code>, що повторюється <var>n</var> разів. Тоді можна погіршити її, обернувши в другий цикл <code>for</code>, такий, що теж повторюється <var>n</var> разів, і отримати у результаті програму з f( n ) = n<sup>2</sup>. Узагальнимо: будь&dash;яка програма зі складністю Θ( <var>a</var> ) також має складність O( <var>b</var> ), якщо <var>b</var> зростає швидше за <var>a</var>. Зверніть увагу, що зміни, внесені в програму, не повинні привести до справної програми або програми, аналогічній початковій. Їй тільки необхідно виконувати більше команд, ніж виконується оригінальною версією програми. Змінену програму ми використовуємо суто для підрахунку команд, а не для розв&apos;язання початкової задачі.</p>

        <p>Отже, безпечніше буде сказати, що наша програма має складність O( n<sup>2</sup> ): ми проаналізували алгоритм і знайшли, що він ніколи не працює гірше, ніж n<sup>2</sup>. Таке формулювання дає нам достатню оцінку швидкості роботи нашої програми. Наступні вправи дано для звикання до нової нотації.</p>

        <div class='exercise'>
            <h3>Вправа 3</h3>

            <p>Визначте вірні формулювання:</p>
            <ol>
                <li>Алгоритм з Θ( n ) має складність O( n )</li>
                <li>Алгоритм з Θ( n ) має складність O( n<sup>2</sup> )</li>
                <li>Алгоритм з Θ( n<sup>2</sup> ) має складність O( n<sup>3</sup> )</li>
                <li>Алгоритм з Θ( n ) має складність O( 1 )</li>
                <li>Алгоритм з O( 1 ) має складність Θ( 1 )</li>
                <li>Алгоритм з O( n ) має складність Θ( 1 )</li>
            </ol>
        </div>

        <div class='exercise solution'>
            <h3>Відповіді</h3>

            <ol>
                <li>Вірно, бо початкова програма має складність Θ( n ). Ми можемо отримати O( n ) навіть не змінюючи програму.</li>
                <li>Вірно, бо n<sup>2</sup> гірше, ніж n.</li>
                <li>Вірно, адже n<sup>3</sup> гірше, ніж n<sup>2</sup>.</li>
                <li>1 не гірше, ніж n, тож це невірне твердження. Якщо програма асимптотично виконує <var>n</var> команд (лінійна кількість), то ми не можемо ускладнити її та отримати лише одну команду, виконувану асимптотично (стала кількість).</li>
                <li>Вірно, бо ці складності рівнозначні.</li>
                <li>Це може бути як вірним, так і невірним твердженням. У загальному випадку воно хибне. Якщо алгоритм має складність Θ( 1 ), тоді він зазвичай має й складність O( n ). Але при O( n ), він не обов&apos;язково буде мати складність Θ( 1 ). Наприклад, алгоритм Θ( n ) має складність O( n ), але не Θ( 1 ).</li>
            </ol>
        </div>

        <div class='exercise'>
            <h3>Вправа 4</h3>

            <p>Скористайтеся формулою суми арифметичної прогресії для доказу, що дана вище програма має складність не тільки O( n<sup>2</sup> ), а й також Θ( n<sup>2</sup> ). Якщо ви не знаєте, що таке арифметична прогресія, загляньте у <a href='https://uk.wikipedia.org/wiki/Арифметична_прогресія'>Вікіпедію</a> &mdash; це легко.</p>
        </div>
	
	<p>Оскільки &laquo;О&raquo; велике алгоритму описує <em>верхню межу</em> дійсної складності алгоритму (що визначається з Θ), то іноді можна сказати, що Θ описує <em>точні межі</em> складності. Якщо відомо, що знайдена межа складності не є точною, то в таких випадках можна використовувати нотацію &laquo;o&raquo; маленьке. Наприклад, якщо алгоритм має складність Θ( n ), тоді його точна складність відповідає n. Отже, цей алгоритм має складність і O( n ), і O( n<sup>2</sup> ). Межа O( n ) є точною, але межа O( n<sup>2</sup> ) &mdash; ні. Так що можна написати, що цей алгоритм має складність o( n<sup>2</sup> ) &mdash; вимовляється &laquo;o маленьке від ен у квадраті&raquo; &mdash; для ілюстрації того, що ця межа неточна. Зазвичай краще знати точні межі алгоритмів, адже таким чином більше стає відомо про поведінку алгоритму. Однак точні межі не завжди легко визначити.</p>

        <div class='exercise'>
            <h3>Вправа 5</h3>

            <p>Визначте, які з перелічених меж точні, а які ні. Перевірте, чи всі межі вірні. Використайте &laquo;О&raquo; велике для ілюстрації неточних меж.</p>

            <ol>
                <li>Алгоритм з Θ( n ) та верхньою межею O( n ).</li>
                <li>Алгоритм з Θ( n<sup>2</sup> ) та верхньою межею O( n<sup>3</sup> ).</li>
                <li>Алгоритм з Θ( 1 ) та верхньою межею O( n ).</li>
                <li>Алгоритм з Θ( n ) та верхньою межею O( 1 ).</li>
                <li>Алгоритм з Θ( n ) та верхньою межею O( 2n ).</li>
            </ol>
        </div>

        <div class='exercise solution'>
            <h3>Відповіді</h3>

            <ol>
                <li>У цьому випадку Θ й O складності однакові, так що це точна межа.</li>
                <li>Тут ми бачимо, що O дає більшу складність, ніж Θ, так що ця межа неточна (складність O( n<sup>2</sup> ) дала б точну межу). Отже, ми можемо записати складність алгоритму у вигляді o( n<sup>3</sup> ).</li>
                <li>Ми знову бачимо, що O дає більшу складність, ніж Θ. Так що це неточна межа (межа O( 1 ) була б точною). Отже, можна позначити, що межа O( n ) неточна, записавши її у вигляді o( n ).</li>
                <li>Ця межа помилкова. Для алгоритму з Θ( n ) неможливо, щоб верхня межа була O( 1 ), адже n має більшу складність, ніж 1. Пам&apos;ятайте, що &laquo;О&raquo; велике описує верхню межу.</li>
                <li>Може здатися, що ця межа неточна, однак це не так. Ця межа насправді точна. Згадайте, що асимптотична поведінка 2n є n; а також що O й Θ описуюсь асимптотичну поведінку. З цього випливає, що O( 2n ) = O( n ), тобто ця межа точна, бо вона дорівнює Θ.</li>
            </ol>
        </div>

        <div class='highlight'>
            <p class='thumb'><strong>Підказка</strong>: Знайти складність &laquo;O&raquo; легше, ніж складність &laquo;Θ&raquo;.</p>
        </div>

        <p>Ймовірно, що всі ці нові форми запису добряче вас вже притомили. Все ж познайомимося ще з двома символами, а потім розглянемо приклади. Ці символи буде легко зрозуміти на базі вже знайомих вам Θ, O та o. Нові символи не будуть вживатися в наступній частині статті, проте добре б їх знати; зараз відповідний момент для такого знайомства. В наведеному вище прикладі, ми змінювали програму так, щоб вона працювала гірше (додавши команди для уповільнення її роботи), і виводили таким чином &laquo;О&raquo; велике. &laquo;O&raquo; надає цінну інформацію, на базі якої можна доводити, що наша програма працює досить добре. Якщо виконати зворотну дію: <strong>поліпшити</strong> програму, щоб потім знайти її складність; теж можна використовувати форму запису &laquo;Ω&raquo;. Ω описує складність таким чином, що ми знаємо: наша програма не працюватиме краще цієї складності. Таке знання корисно в тих випадках, коли ми хочемо показати, що програма працює повільно або що аналізований алгоритм не є ефективним для розв&apos;язання певної задачі. Наприклад, алгоритм зі складністю Ω( n<sup>3</sup> ) означає, що цей алгоритм не працює краще, ніж n<sup>3</sup> (він як мінімум настільки поганий). Тобто цей алгоритм може мати складність Θ( n<sup>3</sup> ), або Θ( n<sup>4</sup> ), або навіть гірше. Отже, Ω дає нам <em>нижню межу</em> складності алгоритму. На зразок &laquo;ο&raquo; маленького, можна використовувати запис у вигляді &laquo;ω&raquo; маленьке тоді, коли відомо, що межа неточна. Наприклад, алгоритм Θ( n<sup>3</sup> ) має ο( n<sup>4</sup> ) та ω( n<sup>2</sup> ). Ω( n ) вимовляється як &laquo;омега велике від ен&raquo;, а ω( n ) вимовляється як &laquo;омега маленьке від ен&raquo;.</p>

        <div class='exercise'>
            <h3>Вправа 6</h3>

            <p>Визначте точні та неточні О і Ω межі наступних Θ складностей.</p>
            <ol>
                <li>Θ( 1 )</li>
                <li>Θ( <img alt='sqrt( n )' src='images/sqrtn.png' /> )</li>
                <li>Θ( n )</li>
                <li>Θ( n<sup>2</sup> )</li>
                <li>Θ( n<sup>3</sup> )</li>
            </ol>
        </div>

        <div class='exercise solution'>
            <h3>Відповіді</h3>

            <ol>
                <li>Точними межами є O( 1 ) і Ω( 1 ). Неточною O межею може бути O( n ). Згадайте, що O дає нам верхню межу. n має більшу складність, ніж 1, тож цю неточну межу можна також записати як o( n ). Неточна Ω межа не існує, бо не можливо спростити складність, що дорівнює 1.</li>
                <li>Точні межі дорівнюються Θ складності, так що це O( <img alt='sqrt( n )' src='images/sqrtn.png' /> ) та Ω( <img alt='sqrt( n )' src='images/sqrtn.png' /> ). В ролі неточної межі можна використовувати O( n ), адже n більше, ніж <img alt='sqrt( n )' src='images/sqrtn.png' />. Знаючи, що це неточна верхня межа, можна використати форму запису o( n ). Для неточної нижньої межі можна використати Ω( 1 ), що також можна записати як ω( 1 ).</li>
                <li>Точними межами є O( n ) і Ω( n ). Неточними межами можуть бути ω( 1 ) та o( n<sup>3</sup> ). Але це досить поганий вибір меж, бо вони сильно відрізняються від початкової складності. Однак вони відповідають даними нами визначенням, тож їх можна використовувати.</li>
                <li>Точними межами є O( n<sup>2</sup> ) і Ω( n<sup>2</sup> ). В ролі неточних меж можна знову використати ω( 1 ) та o( n<sup>3</sup> ), як і в попередньому прикладі.</li>
                <li>Точними межами є O( n<sup>3</sup> ) і Ω( n<sup>3</sup> ). Неточними межами можуть бути ω( <img alt='sqrt( n )' src='images/sqrtn.png' /> n<sup>2</sup> ) та o( <img alt='sqrt( n )' src='images/sqrtn.png' /> n<sup>3</sup> ). Це неточні межі, але все одне вони кращі за ті, що були дані вище.</li>
            </ol>
        </div>

        <p>Причина використання O і Ω замість Θ &mdash; хоча O і Ω також можуть визначати точні межі &mdash; полягає в тому, що не завжди відомо, чи є знайдена межа точної (ймовірно, коли в нас нема бажання прискіпливо аналізувати алгоритм).</p>

	<p>Не хвилюйтеся, якщо ви не запам&apos;ятали всі символи та їх призначення. Ви завжди можете повернутися до цієї статті й уточнити їх дані. Найважливішими символами є O і Θ.</p>

        <p>Також зауважте, що хоча Ω визначає поведінку нижньої межі функції (тобто функція була поліпшена зменшенням кількості виконуваних команд), ми все ще посилаємося на аналіз &laquo;найгіршого випадку&raquo;. Так відбувається тому, що ми даємо програмі самий поганий варіант із можливих вхідних даних; поведінка програми аналізується виходячи з цього припущення.</p>

	<p>Наступна таблиця показує тільки що представлені символи та відповідні їм звичайні математичні символи, використовувані для порівняння чисел. Літери грецького алфавіту використовуються замість більш звичних символів для вказівки, що ми займаємося порівнянням асимптотичної поведінки, а не чисел.</p>

        <div class='figure'>
            <table>
                <thead>
                    <tr>
                        <th>Асимптотичне порівняння</th>
                        <th>Чисельне порівняння</th>
                    </tr>
                </thead>
                <tbody>
                    <tr>
                        <td>Алгоритм з <strong>o</strong>( щось )</td>
                        <td>Число <strong>&lt;</strong> щось</td>
                    </tr>
                    <tr>
                        <td>Алгоритм з <strong>O</strong>( щось )</td>
                        <td>Число <strong>≤</strong> щось</td>
                    </tr>
                    <tr>
                        <td>Алгоритм з <strong>Θ</strong>( щось )</td>
                        <td>Число <strong>=</strong> щось</td>
                    </tr>
                    <tr>
                        <td>Алгоритм з <strong>Ω</strong>( щось )</td>
                        <td>Число <strong>≥</strong> щось</td>
                    </tr>
                    <tr>
                        <td>Алгоритм з <strong>ω</strong>( щось )</td>
                        <td>Число <strong>></strong> щось</td>
                    </tr>
                </tbody>
            </table>
        </div>

        <div class='highlight'>
            <p class='thumb'><strong>Підказка</strong>: Хоча всі символи O, o, Ω, ω і Θ дуже корисні, &laquo;О&raquo; велике використовується найчастіше. Його простіше визначити, ніж Θ, й воно практичніше, ніж Ω.</p>
        </div>

        <div class='right sidefigure'>
            <img src='images/log-vs-linear.png' alt='Навіть при невеликому n, логарифмічна функція розташована набагато нижче функції квадратного кореня, яка, в свою чергу, розташована набагато нижче лінійної функції.' />
            <label><strong>Ілюстрація 4</strong>: Порівняння функцій n, <img alt='sqrt( n )' src='images/sqrtn.png' />, та log( n ). Лінійна функція n (намальована зеленим кольором, розташована вгорі), росте набагато швидше, ніж функція квадратного кореня (намальована червоним кольором, розташована посередині), яка і собі росте набагато швидше, ніж функція log (n) (намальована синім кольором внизу графіка). Навіть для маленьких значень n, таких як n = 100, різниця досить істотна.</label>
        </div>

        <h2 id='logarithms'>Логарифми</h2>

        <p>Якщо ви знаєте, що таке логарифм, то можете пропустити цей розділ. Цей ознайомчий розділ написаний для тих, хто не знайомий із логарифмами; а також для тих, хто давно з ними не стикався. Цей текст також призначений для учнів, які ще не вивчали логарифми в школі. Знання логарифмів дуже важливе, адже вони постійно зустрічаються при аналізі складності алгоритмів. <em>Логарифм</em> &mdash; це операція, застосована до числа так, що число значно зменшується (зовсім як витяг кореня). Витяг квадратного кореня є операцією, зворотною від піднесення числа до квадрату. Так саме, логарифм &mdash; це зворотна операція від піднесення числа до будь-якого степеня. Насправді все набагато простіше, ніж звучить. Краще розглянемо на ось такому прикладі:</p>

        <p>2<sup>x</sup> = 1024</p>

        <p>Для того, щоб розв&apos;язати це рівняння та знайти значення <var>x</var>, ми запитуємо себе: в яку степінь потрібно звести 2, щоб отримати 1024? Це буде число 10. Дійсно, ми отримуємо 2<sup>10</sup> = 1024, що легко підтвердити. Логарифми допомагають записати цю задачку в інший нотації. В цьому випадку 10 є логарифмом 1024, що записується як log( 1024 ) (вимовляється як &laquo;логарифм 1024&raquo;). Позаяк ми використовуємо 2 в основі логарифмів, такі логарифми мають назву двійкових. Існують логарифми з іншими основами, але в цій статті ми використовуємо лише логарифми з основою 2. Якщо ви учень, який бере участь у міжнародних змаганнях і не знайомий з логарифмами, то я вкрай рекомендую вам <a href='https://tutorial.math.lamar.edu/Classes/Alg/LogFunctions.aspx'>попрактикуватися</a> після прочитання цієї статті. В інформатиці двійкові логарифми зустрічаються частіше, ніж інші типи логарифмів. Все через те, що в інформатиці ми в базі маємо лише дві сутності: 0 та 1; і воліємо розбивати великі проблеми на дві частини (повторюючи цю дію). Отже, для подальшого читання статті вам необхідні тільки двійкові логарифми.</p>

        <div class='exercise'>
            <h3>Вправа 7</h3>

	<p>Розв&apos;яжіть рівняння. Запишіть знайдені логарифми. Використовуйте тільки двійкові логарифми.</p>
            <ol>
                <li>2<sup>x</sup> = 64</li>
                <li>(2<sup>2</sup>)<sup>x</sup> = 64</li>
                <li>4<sup>x</sup> = 4</li>
                <li>2<sup>x</sup> = 1</li>
                <li>2<sup>x</sup> + 2<sup>x</sup> = 32</li>
                <li>(2<sup>x</sup>) * (2<sup>x</sup>) = 64</li>
            </ol>
        </div>

        <div class='exercise solution'>
            <h3>Відповіді</h3>

            <p>Просто використовуйте ідеї, дані вище.</p>
            <ol>
                <li>Методом проб і помилок знаходимо, що x = 6 і log( 64 ) = 6.</li>
                <li>Згідно з властивостями степеня, (2<sup>2</sup>)<sup>x</sup> можна записати як 2<sup>2x</sup>. Застосовуючи попередній результат log( 64 ) = 6, ми отримуємо, що 2x = 6. Отже, x = 3.</li>
                <li>Використовуючи дані з попереднього рівняння, можна записати 4 у вигляді 2<sup>2</sup>, так що рівняння перетворюється в (2<sup>2</sup>)<sup>x</sup> = 4, а це те ж саме, що 2<sup>2x</sup> = 4. Потім ми помічаємо, що log( 4 ) = 2 (адже 2<sup>2</sup> = 4) і, отже, ми отримуємо, що 2x = 2. Тобто x = 1. Цей результат легко підтвердити, бо піднесення числа до степеня 1 повертає само число.</li>
                <li>Згадаймо, що піднесення числа до степеня 0 дає в результаті 1. Значить, 2<sup>0</sup> = 1, тобто x = 0 і log( 1 ) = 0.</li>
                <li>Тут ми маємо справу зі складанням, так що не можемо визначити логарифм безпосередньо. Однак ми помічаємо, що 2<sup>x</sup> + 2<sup>x</sup> дорівнюється 2 * (2<sup>x</sup>). Отже, у нас з&apos;явився множник 2, тоді цей вираз можна записати у вигляді 2<sup>x + 1</sup>. Тепер нам залишилося тільки розв&apos;язати рівняння 2<sup>x + 1</sup> = 32. Ми знаходимо, що log( 32 ) = 5 і тоді x + 1 = 5. Отже, x = 4.</li>
                <li>Ми множимо результати піднесення 2 до степеня x, тобто ми можемо об&apos;єднати множники, помітивши, що (2<sup>x</sup>) * (2<sup>x</sup>) дорівнюється 2<sup>2x</sup>. Потім усе, що нам треба зробити &mdash; це розв&apos;язати рівняння 2<sup>2x</sup> = 64, яке ми вже розв&apos;язували з результатом x = 3.</li>
            </ol>
        </div>

        <div class='highlight'>
            <p class='thumb'><strong>Підказка</strong>: У випадку з алгоритмами, написаними для змагань (на мові C ++), як тільки складність була проаналізована, можна отримати орієнтовну оцінку швидкості роботи вашої програми. Чекайте продуктивність близько 1,000,000 операцій в секунду (для операцій, кількість яких визначено функцією асимптотичної поведінки алгоритму). Наприклад, алгоритм зі складністю Θ (n) відпрацьовує приблизно за секунду при розмірі вхідних даних n = 1,000,000.</p>
        </div>

        <div class='right sidefigure'>
            <img src='images/factorial-recursion.png' alt='factorial( 5 ) -&gt; factorial( 4 ) -&gt; factorial( 3 ) -&gt; factorial( 2 ) -&gt; factorial( 1 )' />
            <label><strong>Ілюстрація 5</strong>: Рекурсія, виконувана функцією факторіала.</label>
        </div>

        <h2 id='recursion'>Складність рекурсивних алгоритмів</h2>

        <p>Розглянемо рекурсивні функції. <em>Рекурсивною</em> називається функція, яка викликає саму себе. Чи піддається аналізу складність таких функцій? Наступна функція, написана на мові Python, обчислює <a href='https://uk.wikipedia.org/wiki/Факторіал'>факторіал</a> числа. Факторіал позитивного цілого числа знаходиться за допомогою множення початкового числа з кожним попереднім йому позитивним цілим числом. Наприклад, факторіал числа 5 дорівнює 5 * 4 * 3 * 2 * 1. Факторіал записується у вигляді &laquo;5!&raquo;, що вимовляється як &laquo;п&apos;ять факторіал&raquo; (хоча деякі люди полюбляють голосно викрикувати &laquo;П&apos;ЯТЬ!!!&raquo;)</p>

        <div class='leftofimage'>
            <pre class='brush: python; gutter: false; toolbar: false;'>
                def factorial( n ):
                    if n == 1:
                        return 1
                    return n * factorial( n - 1 )
            </pre>
        </div>

        <p>Проаналізуємо складність цієї функції. Вона не містить циклів, але її складність все ж не є сталим значенням. Для визначення складності нам треба знову зайнятися підрахунком команд, які виконуються програмою. Очевидно, що якщо передати в цю програму деяке значення <var>n</var>, то вона відпрацює <var>n</var> разів. Якщо ви не впевнені в цьому, то перевірте &laquo;вручну&raquo;, яким чином функція відпрацює при n = 5. Ви побачите, що функція буде викликана 5 разів, кожен раз зменшуючи n на 1. Отже, функція має складність Θ( n ).</p>

        <p>Якщо ви все ще не впевнені в цьому факті, згадайте, що завжди можна знайти точну складність, підрахувавши кількість виконуваних команд. Якщо хочете, спробуйте підрахувати реальну кількість команд, які виконуються функцією факторіала, виведіть f (n) і переконайтеся, що вона на ділі лінійна (нагадую, що лінійна функція відповідає Θ (n)).</p>

        <p><strong>Ілюстрація 5</strong> містить діаграму, яка допоможе вам зрозуміти, як виглядає рекурсія при виконанні функції factorial (5), і чому ця функція має лінійну складність.</p>

        <div class='right sidefigure'>
            <img src='images/binary-search.png' alt='Двійковий пошук у масиві' />
            <label><strong>Ілюстрація 6</strong>: Рекурсія, виконувана двійковим пошуком. Аргумент A кожного виклику виділено чорним кольором. Рекурсивні виклики тривають доки в досліджуваному масиві не залишиться один елемент. (Використано з дозволу Luke Francl).</label>
        </div>

        <h2 id='logcomplexity'>Логарифмічна Складність</h2>

        <p>Одна з класичних задач в інформатиці &mdash; це пошук значення в масиві. Ми вже стикалися з таким завданням в одному з попередніх розділів. Пошук у масиві стає дуже цікавим, якщо нам дано вже відсортований масив. Один зі способів пошуку у відсортованому масиві називається <em>двійковим</em>. При такому способі перевіряється елемент у середині масиву: якщо знайдено шукане значення, то пошук закінчений; якщо значення середини більше, ніж шукане, то пошук продовжується в лівій частині масиву; інакше пошук продовжується в правій частині масиву. Потім отримані менші масиви знову розбиваються навпіл, доки не залишиться лише один елемент. Ось цей метод записаний за допомогою псевдокоду:</p>

        <div class='leftofimage'>
            <pre class='brush: python; gutter: false; toolbar: false;'>
                def binarySearch( A, n, value ):
                    if n = 1:
                        if A[ 0 ] = value:
                            return true
                        else:
                            return false
                    if value &lt; A[ n / 2 ]:
                        return binarySearch( A[ 0...( n / 2 - 1 ) ], n / 2 - 1, value )
                    else if value &gt; A[ n / 2 ]:
                        return binarySearch( A[ ( n / 2 + 1 )...n ], n / 2 - 1, value )
                    else:
                        return true
            </pre>
        </div>

        <p>Цей псевдокод є спрощеною версією реальної реалізації двійкового пошуку. На практиці двійковий пошук легше описати, ніж реалізувати в коді. Адже програмістам треба подбати про всі деталі: помилку неврахованої одиниці (англ. off-by-one error), необхідності округлення результатів розподілу на 2 і таке інше. Ми лише бажаємо проаналізувати складність цього алгоритму, тому припустимо, що він завжди працює успішно, і що реальна імплементація подбає про всі необхідні деталі. Якщо ви ніколи не реалізовували двійковий пошук, рекомендую зробити це на вашій улюбленій мові програмування. Це дійсно просвітницьке зайняття.</p>

        <p><strong>Ілюстрація 6</strong> повинна допомогти вам зрозуміти, як працює двійковий пошук.</p>

        <p>Якщо ви не впевнені в працездатності цього методу, візьміть простий приклад і переконайтеся, що він дійсно працює.</p>

        <p>Зараз спробуємо проаналізувати цей алгоритм. Тут ми знову зіткнулися з рекурсією. Припустимо для простоти, що масив завжди ділиться рівно навпіл, і проігноруймо <code>+ 1</code> і <code>- 1</code> у рекурсивних викликах. Ви вже повинні розуміти, що така маленька зміна, як ігнорування <code>+ 1</code> і <code>- 1</code>, не вплине на результати аналізу складності. Нам довелося б доводити цей факт, якби ми хотіли бути точними з математичної точки зору, але він і так інтуїтивно зрозумілий. Також для простоти припустимо, що нам дано масив із розміром, що дорівнює степеню 2. Це припущення теж не вплине на кінцевий результат аналізу складності. Найгірший випадок цього завдання буде отримано, якщо шуканого значення взагалі немає в масиві. В такому випадку при першому виклику функції алгоритм отримає масив із розміром n. При наступному, рекурсивному, виклику: n / 2. Після цього рекурсивний виклик отримає масив із розміром n / 4, потім масив із розміром n / 8 і так далі. Масив розбивається навпіл при кожному новому рекурсивному виклику, поки не досягне розміру 1. Отже, запишемо кількість елементів масиву при кожному виклику:</p>
        <ol class='hide-nums'>
            <li>0-ва ітерація: n</li>
            <li>1-ша ітерація: n / 2</li>
            <li>2-га ітерація: n / 4</li>
            <li>3-тя ітерація: n / 8</li>
            <li>...</li>
            <li>i-та</sup> ітерація: n / 2<sup>i</sup></li>
            <li>...</li>
            <li>остання ітерація: 1</li>
        </ol>

        <p>Зверніть увагу, що на <i>i</i>-му кроці масив має n / 2<sup>i</sup> елементів. Так відбувається тому, що на кожному кроці масив поділяється навпіл (іншими словами, ми ділимо кількість елементів масиву на 2). Цю дію можна виразити у вигляді множення знаменника на 2. Роблячи таку операцію <var><i>i</i></var> разів, отримуємо n / 2<sup>i</sup>. Потім процедура розподілу триває, для все більшого <var><i>i</i></var> ми отримуємо все меншу кількість елементів, доки не досягнемо останнього кроку, на якому залишається лише 1 елемент. Якщо ми хочемо знайти <var><i>i</i></var>, щоб дізнатися кількість кроків роботи програми, необхідно знайти рішення наступного рівняння:</p>

        <p>1 = n / 2<sup>i</sup></p>

        <p>Це рівняння стане вірним лише тоді, коли ми доберемося до останнього виклику функції binarySearch(), не в загальному випадку. Знайшовши <var><i>i</i></var>, ми знайдемо, на якому етапі закінчаться рекурсивні виклики. Помноживши обидві сторони на 2<sup>i</sup>, отримуємо:</p>

        <p>2<sup>i</sup> = n</p>

        <p>Це рівняння має виглядати знайомим, якщо ви прочитали розділ про логарифми. Розв&apos;язавши рівняння для <var><i>i</i></var>, отримуємо:</p>

        <p>i = log( n )</p>

        <p>Цей вираз показує нам, що кількість кроків, необхідних для здійснення двійкового пошуку, дорівнюється log( n ), де n &mdash; кількість елементів у масиві.</p>

        <p>Такий результат виглядає цілком реалістично. Наприклад, візьміть n = 32, масив із 32 елементами. Скільки разів нам доведеться ділити масив навпіл, щоб отримати 1 елемент? Ми отримаємо: 32 → 16 → 8 → 4 → 2 → 1 елементів, виконавши 5 кроків, що і є логарифм 32. Отже, складність двійкового пошуку дорівнює Θ( log( n ) ).</p>

        <p>Останній результат дозволяє нам порівняти двійковий пошук із лінійним пошуком (попередній з розглянутих нами методів). Очевидно, що log (n) набагато менший, ніж n; тож ми робимо висновок, що двійковий пошук шукає елементи в масиві набагато швидше, ніж лінійний пошук. Також можна порекомендувати підтримувати масиви відсортованими, якщо необхідно часто здійснювати пошук у них.</p>

        <div class='highlight'>
            <p class='thumb'><strong>Підказка</strong>: Поліпшення асимптотичного часу роботи програм також часто значно покращує їх час роботи. І в набагато більших масштабах, ніж будь-які дрібні &laquo;технічні&raquo; оптимізації, як, наприклад, використання більш швидкої мови програмування.</p>
        </div>

        <h2 id='sort'>Оптимальне сортування</h2>

        <p><strong>Вітаю.</strong> Тепер ви знаєте, що таке аналіз складності алгоритмів, асимптотична поведінка й &laquo;О&raquo; велике. Тепер ви знаєте, що таке складність алгоритму O( 1 ), O( log( n ) ), O( n ), O( n<sup>2</sup> ) і так далі. Ви розумієте значення символів o, O, ω, Ω і Θ, а також що таке аналіз найгіршого випадку. Раз ви дісталися до цього етапу, значить навчальний матеріал впорався зі своїм завданням.</p>

        <p>Цей фінальний розділ необов&apos;язковий для прочитання. Він складніший, так що можете опустити його, якщо відчуєте, що ви перевантажені. Цей розділ потребує від вас фокусування для опрацювання додаткових вправ. При цьому, він покаже вам дуже корисний і потенційно потужний метод аналізу складності алгоритмів, що може стати вартим вкладання ваших сил.</p>

        <p>Вище ми розглядали реалізацію алгоритму під назвою сортування вибором. Було згадано, що сортування вибором не є оптимальним алгоритмом. <em>Оптимальним</em> називається алгоритм, який вирішує завдання найкращим способом. Це означає, що всі інші алгоритми розв&apos;язання цієї ж задачі мають складність гіршу чи таку ж, як у оптимального алгоритму. Для розв&apos;язання задач певної складності існує безліч оптимальних алгоритмів. Зокрема, завдання сортування можна вирішити оптимально різними способами. Наприклад, можна використати ідею, що лежить в основі двійкового пошуку, щоб отримати швидкий спосіб сортування, який називається <em>сортування злиттям</em> (англ. merge sort).</p>

        <p>Щоб виконати сортування злиттям, спочатку необхідно написати допоміжну функцію, яка буде використана під час самого сортування. Ми створимо функцію <code>merge</code>. Ця функція приймає два відсортованих масивів і з'єднує (англ. merge: злиття) їх разом, в один упорядкований масив. Це легко зробити:</p>

        <pre class='brush: python; gutter: false; toolbar: false;'>
            def merge( A, B ):
                if empty( A ):
                    return B
                if empty( B ):
                    return A
                if A[ 0 ] &lt; B[ 0 ]:
                    return concat( A[ 0 ], merge( A[ 1...A_n ], B ) )
                else:
                    return concat( B[ 0 ], merge( A, B[ 1...B_n ] ) )
        </pre>

        <p>Функція concat приймає елемент (&laquo;голову&raquo;) та масив (&laquo;хвіст&raquo;), потім будує і повертає новий масив, що містить &laquo;голову&raquo; на першій позиції нового масиву, а елементи &laquo;хвоста&raquo; на решті позицій масиву. Наприклад, concat( 3, [ 4, 5, 6 ] ) повертає [ 3, 4, 5, 6 ]. Ми використовуємо A_n і B_n для позначення розмірів масиву A та B.</p>

        <div class='exercise'>
            <h3>Вправа 8</h3>

            <p>Перевірте, що дана вище функція дійсно виконує злиття. Перепишіть її на своїй улюбленій мові програмування, використовуючи цикл <code>for</code> замість рекурсії.</p>
        </div>

        <p>Аналіз цього алгоритму показує, що час його виконання Θ( n ), де n є розміром кінцевого масиву (n = A_n + B_n).</p>

        <div class='exercise'>
            <h3>Вправа 9</h3>

            <p>Перевірте, що час роботи функції merge <code>merge</code> є Θ( n ).</p>
        </div>

        <p>Використовуючи цю функцію, можна побудувати покращений алгоритм сортування. Базова ідея: ділити масив на дві частини. Ми сортуємо кожну з двох частин рекурсивно, а потім об&apos;єднуємо два впорядковані масиви в один великий масив. Псевдокод:</p>

        <pre class='brush: python; gutter: false; toolbar: false;'>
        def mergeSort( A, n ):
            if n = 1:
                return A # впорядкований масив
            middle = floor( n / 2 )
            leftHalf = A[ 1...middle ]
            rightHalf = A[ ( middle + 1 )...n ]
            return merge( mergeSort( leftHalf, middle ), mergeSort( rightHalf, n - middle ) )
        </pre>

        <p>Цю функцію складніше зрозуміти, ніж те, що ми вже розглядали, отже для наступної вправи може знадобитися більше часу.</p>

        <div class='exercise'>
            <h3>Вправа 10</h3>

            <p>Перевірте, що функція <code>mergeSort</code> працює вірно. А саме, що вона дійсно сортує даний їй масив. Якщо ви не розумієте, як ця функція працює, то візьміть маленький масив і відстежте &laquo;вручну&raquo; кроки, виконувані <code>mergeSort</code>. При цьому ви переконаєтеся, що leftHalf і rightHalf утворюються при розбитті масиву <i>приблизно</i> посередині; розбиття не обов'язково відбувається точно в центрі масиву, якщо він містить непарну кількість елементів (з цієї причини використовується функція <code>floor</code>).</p>
        </div>

        <p>Як останній приклад, піддамо аналізу складність <code>mergeSort</code>. На кожному етапі виконання <code>mergeSort</code>, масив розбивається на дві частини однакового розміру, зовсім як при <code>binarySearch</code>. Однак у разі сортування обидві частини зберігаються в процесі виконання програми. Алгоритм застосовується рекурсивно до кожної з частин. До результату виконання рекурсій застосовується операція <code>merge</code>, яка займає Θ( n ) часу.</p>

        <p>Отже, ми розбиваємо початковий масив на два масиви, кожен із розміром n / 2. Потім ми об'єднуємо ці нові масиви, і ця дія об'єднання n елементів вимагає Θ (n) часу.</p>

        <p>Гляньте на <strong>Ілюстрацію 7</strong>, щоб краще зрозуміти, що відбувається.</p>

        <div class='sidefigure'>
            <img src='images/mergesort-recursion.png' alt='N розбивається на N / 2 і N / 2, кожен з котрих розбивається на N / 4 і N / 4. Цей процес триває до отримання розміру в один елемент.' />
            <label><strong>Ілюстрація 7</strong>: Дерево рекурсії для сортування злиттям.</label>
        </div>

        <p>Подивимося, що тут відбувається. Кожне коло відображає виклик функції <code>mergeSort</code>. Число всередині кола показує розмір сортованого масиву. Верхнє синє коло &mdash; це початковий виклик <code>mergeSort</code>, із завданням впорядкувати масив із розміром <var>n</var>. Стрілки показують рекурсивні виклики функції. Початковий виклик <code>mergeSort</code> робить два рекурсивних запита до <code>mergeSort</code>, передаючи кожного разу один масив із розміром n / 2. Ця дія відображається двома стрілками вгорі картинки. Своєю чергою, кожен із викликів функції робить ще два виклики <code>mergeSort</code>, передаючи кожного разу масив із розміром n / 4 і так далі, поки не будуть отримані масиви з одним елементом. Така схема називається <em>рекурсивним деревом</em>, тому що вона відображає послідовність рекурсивних викликів і схожа на дерево (точніше на перевернуте дерево, <em>корінь</em> якого розташований вгорі, а <em>листя</em> &mdash; внизу).</p>

        <p>Зверніть увагу, що в кожнім ряду схеми загальна кількість елементів завжди дорівнюється n. Щоб побачити це, розгляньте кожен ряд окремо. Перший ряд містить тільки один виклик <code>mergeSort</code> із масивом, який має розмір <var>n</var>, так що загальна кількість елементів дорівнюється <var>n</var>. Другий ряд містить два виклики <code>mergeSort</code>, де кожен із масивів має розмір n / 2. Але n / 2 + n / 2 = n, так що знову загальна кількість елементів у цьому ряду дорівнюється <var>n</var>. У третьому ряду ми бачимо 4 виклики, кожен з яких обробляє масив із розміром n / 4, в результаті даючи загальну кількість елементів n / 4 + n / 4 + n / 4 + n / 4 = 4n / 4 = n. Отже, знову ми отримуємо <var>n</var> елементів. Тепер зверніть увагу, що в кожнім ряду схеми функція, яка робить виклик, повинна буде виконати операцію <code>merge</code> з поверненими елементами. Наприклад, коло, позначене червоним кольором, повинно впорядкувати n / 2 елементів. Щоб зробити це, воно розбиває масив із розміром n / 2 на два масиви з розміром n / 4, викликає рекурсивно <code>mergeSort</code> для їх сортування (ці виклики відображені колами зеленого кольору), потім об&apos;єднує результати в один масив. Операція об&apos;єднання працює з n / 2 елементами. В кожнім ряду дерева загальна кількість поєднуваних елементів дорівнює n. У щойно розглянутому ряду функція об&apos;єднує n / 2 елементів; функція праворуч від неї (показана синім кольором) теж об'єднує n / 2 елементів. Разом маємо n об&apos;єднаних елементів у аналізованому ряду схеми.</p>

        <p>Відповідно до цих міркувань, кожен ряд має складність Θ (n). Нам відомо, що кількість рядів &mdash; відома під назвою <em>глибина</em> дерева рекурсії &mdash; у схемі  дорівнюється log( n ). Це виводиться так само як було зроблено під час аналізу складності двійкового пошуку. Маючи кількість рядів log (n), при тому, що кожен із них має складність Θ (n), складність <code>mergeSort</code> дорівнюється Θ( n * log( n ) ). Це набагато кращий результат, ніж Θ( n<sup>2</sup> ), який ми отримуємо при сортуванні вибором (нагадую, що значення log( n ) набагато менше, ніж n; так що n * log( n ) набагато менше, ніж n * n = n<sup>2</sup>). Якщо все це звучить занадто складно для вас, не турбуйтеся: таку інформацію непросто зрозуміти з першого разу; прочитайте цей розділ ще раз після того, як ви самі спробуєте реалізувати сортування злиттям і переконаєтеся, що воно працює.</p>

        <p>Як було показано в останньому прикладі, аналіз складності дозволяє нам порівнювати алгоритми між собою для з'ясування, який з них працює краще. Тепер ми цілком впевнені, що для великих масивів даних сортування злиттям працює швидше, ніж сортування вибором. Прийти до цього висновку було б важко без теоретичних знань, представлених у цій статті та необхідних для аналізу алгоритмів. На практиці дійсно використовують алгоритми сортування з часом роботи Θ (n * log (n)). Наприклад, <a href='https://github.com/torvalds/linux/blob/master/lib/sort.c'>ядро Linux використовує алгоритм під назвою пірамідальне сортування (англ. heapsort)</a>,  з тим же часом роботи, що й у сортування злиттям, розглянутого нами  &mdash; а саме Θ( n log( n ) ) &mdash;  і який є оптимальним алгоритмом. Зверніть увагу: ми не доводили, що ці алгоритми оптимальні. Для цього нам знадобилася б складніша математична аргументація. Однак можу вас запевнити, що з точки зору складності алгоритмів, сортування не можна зробити більш ефективним.</p>

        <p>Знання про аналіз складності алгоритмів, які ви придбали під час читання цієї статті, повинні допомогти вам створювати швидші програми й фокусувати зусилля, прикладені для оптимізації коду, на дійсно значущих речах; таким чином роблячи вас продуктивнішим. Також, математичну мову та позначення, з якими ви познайомилися у цій статті, допоможуть вам при спілкуванні з іншими програмістами. Тепер ви зможете обговорювати час роботи алгоритмів, використовуючи отримані знання.</p>

        <h2 id='about'>Післяслово</h2>
        <p>Ця стаття ліцензується з <a href='https://creativecommons.org/licenses/by/3.0/deed.uk'>Creative Commons 3.0 Attribution</a>. Це означає, що статтю можна копіювати, поширювати, публікувати на вашому ресурсі, змінювати, та й взагалі робити з нею все, що забажається &mdash; при цьому вказавши моє ім'я. Якщо ви базуєте свою статтю на моїй, то ви не зобов'язані, але я вам пропоную також опублікувати ваш текст із ліцензією Creative Commons, щоб іншим людям було легше ділитися та співпрацювати. Відповідно до цього, ось роботи, що я використав: <a href='http://p.yusukekamiyamane.com/'>fugue icons</a>, <a href='http://leaverou.me/css3patterns/'>Lea Verou</a>. І, найважливіше, я зміг написати цю статтю завдяки знанням, отриманим від професорів <a href='http://www.softlab.ntua.gr/~nickie/'>Nikos Papaspyrou</a> і <a href='http://www.softlab.ntua.gr/~fotakis/'>Dimitris Fotakis</a>.</p>

        <p>Я являюся PhD кандидатом в області криптографії в <a href='http://di.uoa.gr'>Афінському університеті</a>. Коли я писав цю статтю, я був студентом факультету <a href='http://ece.ntua.gr/'>Електротехніки та комп'ютерних наук</a> <a href='http://ntua.gr/'>Афінського національного технічного університету</a>, спеціалізуючись у <a href='http://www.cslab.ntua.gr'>програмному забезпеченні</a> та бувши тренером з <a href='http://pdp.gr/'>Грецьких змагань в області інформатики</a>. Як програміст практик, я був у команді, що побудувала <a href='http://www.deviantart.com/'>deviantART</a>, соціальну мережу для художників; у командах безпеки в <a href='https://www.google.com'>Google</a> і <a href='https://twitter.com'>Twitter</a>; а також у стартапах Zino і Kamibu, які займалися соціальними мережами і розробкою відеоігор. Якщо вам сподобалася стаття, підписуйтесь у <a href='http://www.twitter.com/dionyziz'>Twitter</a> або <a href='http://github.com/dionyziz'>GitHub</a>. <a href='mailto:dionyziz@gmail.com'>Надішліть e-mail</a>, якщо хочете зв'язатися зі мною або зайнятися перекладом цього тексту.</p>

        <p><strong>Дякую вам за читання.</strong> Мені не платили за написання цієї статті, тож, якщо вона вам сподобалася, <a href='mailto:dionyziz@gmail.com'>відправте мені e-mail</a> із привітанням. Мені подобається отримувати фотографії з усього світу. Якщо забажаєте, надсилайте ваше фото в місті, де ви живете!</p>

        <h2 id='references'>Ресурси</h2>
        <ol>
            <li>Cormen, Leiserson, Rivest, Stein. <a href='http://www.amazon.co.uk/Introduction-Algorithms-T-Cormen/dp/0262533057/ref=sr_1_1?ie=UTF8&amp;qid=1341414466&amp;sr=8-1'>Introduction to Algorithms</a>, MIT Press.</li>
            <li>Dasgupta, Papadimitriou, Vazirani. <a href='http://www.amazon.co.uk/Algorithms-Sanjoy-Dasgupta/dp/0073523402/ref=sr_1_1?s=books&amp;ie=UTF8&amp;qid=1341414505&amp;sr=1-1'>Algorithms</a>, McGraw-Hill Press.</li>
            <li>Fotakis. Course of <a href='http://discrete.gr/'>Discrete Mathematics</a> at the National Technical University of Athens.</li>
            <li>Fotakis. Course of <a href='http://www.corelab.ece.ntua.gr/courses/algorithms/'>Algorithms and Complexity</a> at the National Technical University of Athens.</li>
        </ol>

       <div id="disqus_thread"></div>
<?php
    return array(
        'title' => 'Доступне введення в аналіз складності алгоритмів.',
        'content' => ob_get_clean()
    );
?>