Асимптотичний аналіз

Часто корисно оцінити, скільки часу працює алгоритм. Звичайно, можна його просто реалізувати та запустити, але тут виникають проблеми:

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

Для цього, як перший наближення, спробуємо оцінити кількість операцій у алгоритмі. Виникає питання: які саме операції рахувати. Як один із варіантів — враховувати будь-які елементарні операції:

• арифметичні операції з числами: +, -, *, /
• порівняння чисел: , =, ==, !=
• привласнення: a[0] = 3

При цьому важливо не просто рахувати рядки, а ще враховувати, як реалізовані деякі окремі речі в самій мові. Наприклад, у пітоні зрізи масиву (array[3:10]) копіюють цей масив, тобто цей зріз працює за 7 елементарних дій. А swap, наприклад, можна реалізувати за 3 присвоєння.

Вправа. Спробуйте порахувати точне число порівнянь і привласнювань у сортуваннях бульбашкою, вибором, вставками та підрахунком у гіршому випадку. Це має бути якась формула, яка залежить від $n$ — довжини масиву.

Щоб врахувати взагалі всі елементарні операції, ще треба порахувати, наприклад, скільки разів додалася одиниця всередині циклу for . А ще, наприклад, рядок n = len (array) це теж дія. Тому навіть порахувавши їх, не одразу очевидно, який із цих алгоритмів працює швидше — порівнювати формули складно.Хочеться придумати спосіб спростити ці формули так, щоб

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

Для цього вигадали О-нотацію — асимптотичний час роботи замість точного (часто його ще називають просто асимптотикою).

Визначення. Нехай $f(n)$ це якась функція. Говорять, що функція $g(n) = O(f(n))$, якщо є такі константи $c$ і $n_0$, що $g(n) < c \cdot f(n)$ всім $n \geq n_0$.

• $\frac= O(n)$
• $\frac= O(n^3)$
• $1 + 2 + 3 + \ldots + n = O(n^2)$
• $1^2 + 2^2 + 3^2 + \ldots + n^2 = O(n^3)$
• $ \ log_2 + 3 = O (\ log n) $
• $179 = O(1)$
• $10^ = O(1)$

У контексті аналізу алгоритмів, фраза «алгоритм працює за $O(f(n))$ операцій» означає, що з якогось $n$ він робить лише за $c \cdot f(n)$ операцій.

У таких позначеннях можна сказати, що

• сортування бульбашкою працює за $ O (n ^ 2) $;
• сортування вибором працює за $O(n^2)$;
• сортування вставками працює за $O(n^2)$;
• сортування підрахунком працює за $O(n+m)$.

Це позначення зручне тим, що воно коротке та зрозуміле, а також не залежить від множення на константу чи додавання константи. Наприклад, якщо алгоритм працює за $O(n^2)$, це може означати, що він працює за $n^2$, за $n^2 + 3$, за $\frac$ або навіть за $1000 \cdot n^2 + 1 $ дію. Головне — що функція поводиться як $n^2$, тобто при збільшенні $n$ вона збільшується як деяка квадратична функція: якщо збільшити $n$ в 10 разів, час роботи програми збільшиться приблизно в 100 разів.

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

Перші три сортування тому називають квадратичними - Вони працюють за $ O (n ^ 2) $. Сортування підрахунком може працювати набагато швидше — воно працює за $O(n + m)$, а якщо $m \leq n$, це взагалі лінійна функція $O(n)$.

Асимптотичний аналіз алгоритмів

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

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

Основні оцінки зростання, що зустрічаються в асимптотичному аналізі:

• Ο (О-велике) - верхня асимптотична оцінка зростання тимчасової функції;
• Ω (Омега) – нижня асимптотична оцінка зростання часової функції;
• Θ (Тета) – нижня та верхня асимптотичні оцінки зростання тимчасової функції.

Нехай n - Величина обсягу даних. Тоді зростання функції алгоритму f(n) можна обмежити функцій g(n) асимптотично:

Наприклад, час прибирання приміщення лінійно залежить від площі цього приміщення (Θ(S)), т.е. е.зі зростанням площі в n раз, час збирання збільшитися також у n разів. Пошук імені телефонної книги потребує лінійного часу Ο(n), якщо скористатися алгоритмом лінійного пошуку, або часу, що логарифмічно залежить від числа записів (Ο(log₂(n))), у разі застосування двійкового пошуку.

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

Під фразою «складність алгоритму є Ο(f(n))» мається на увазі, що зі збільшенням обсягу вхідних даних n, час роботи алгоритму зростатиме не швидше, ніж деяка константа, помножена на f(n).

Важливі правила асимптотичного аналізу:

1. O(k*f) = O(f) – постійний множник k (константа) відкидається, оскільки зі зростанням обсягу даних, його зміст втрачається, наприклад:

O(9,1n) = O(n)

1. O(f*g) = O(f)*O(g) – оцінка складності твору двох функцій дорівнює твору їх складнощів, наприклад:

O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2 )

1. O(f/g)=O(f)/O(g) – оцінка складності приватного двох функцій дорівнює приватному їх складнощів, наприклад:

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)

1. O(f+g) дорівнює домінанті O(f) та O(g) – оцінка складності суми функцій визначається як оцінка складності домінанти першого та другого доданків, наприклад:

O(n 5 +n 10 ) = O(n 10 )

Підрахунок кількості операцій – справа стомлива і, що важливо, зовсім не обов'язкова. Виходячи з вище перерахованих правил, щоб визначити складність алгоритму, не потрібно, як ми це робили раніше, вважати всі операції, достатньо знати, якою складністю володіє та чи інша конструкція алгоритму (оператор або група операторів).Так, алгоритм, що не містить циклів та рекурсій, має константну складність O(1). Складність циклу, що виконує n ітерацій, дорівнює O(n). Конструкція їх двох вкладених циклів, що залежать від однієї і тієї ж змінної nмає квадратичну складність O(n 2 ).

Ось найчастіше зустрічаються класи складності:

• O(1) – константна складність;
• Про(n) - Лінійна складність;
• Про(nа ) – поліноміальна складність;
• Про(Log (n)) - логарифмічна складність;
• O(n*log(n)) – квазілінійна складність;
• O(2 n ) – експоненційна складність;
• O(n!) - Факторіальна складність.

Алгоритмічна складність

Алгоритмічна складність – тема окремого курсу у класичних університетських програмах. Як, утім, і математичний аналіз. Однак на співбесіді Вас навряд чи попросять порахувати інтеграл, а ось про складність алгоритмів запитують практично всіх на будь-яку позицію програміста. Чи знайоме Вам поняття алгоритмічна складність? А яка складність швидкого сортування? А це в кращому чи в найгіршому випадку? Буває, з горем навпіл розібралися з якимось завданням на логіку, але вас добивають: а яка складність Вашого рішення, чи можна прискорити? У цьому посту постараюся пояснити, що тут до чого, і не лякайтеся, якщо для Вас NP-повнота означає не більше ніж NP-порожнеча.

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

Складність алгоритму - це у відповідь питання скільки дій доведеться зробити, щоб розв'язати завдання, залежно від параметрів завдання. Різнорідних параметрів у завданні може бути багато, і різнорідних дій теж. І те й інше потрібно скоротити до одного: один параметр та одну дію, іншу відкинути. Наприклад, Ви гортаєте договір із тисячі сторінок та підписуєте кожну. Вхідний параметр такого завдання буде кількість сторінок, а дія – поставити підпис. Перегортання сторінок ми не вважаємо за важливу дію, тому що це набагато швидше за підпис. Не важливо, скільки часу піде на все, дві години чи два дні – хтось розписується швидше, хтось повільніший. Але кожному потрібно 1000 дій для виконання алгоритму. Якщо узагальнити, потрібно дій N при N сторінках. Легко можна порахувати, що якщо Ви підписали договір з 10 сторінок за 10 хвилин, то на 60 сторінок Ви витратите годину. Якщо оптимізувати процес і підписувати лише першу сторінку, потрібно одну хвилину незалежно від кількості сторінок.

Інший приклад - на папері розлинований квадрат зі стороною 10. У кожній клітці потрібно поставити крапку, всього 100 точок (N^2). Якщо потрібно 10 хвилин на все про все, то щоб повторити алгоритм на квадраті зі стороною 60, потрібно 10 / 100 * 60 * 60 = 360 хвилин, тобто 6 годин. Разом в одному завданні збільшивши вхідний параметр у шість разів, ми витратили у 6 разів більше часу, а в іншому – у 36. Різниця колосальна.

Я навів три приклади складності алгоритму: константну, порядку N та порядку N^2.У програмістів прийнято говорити "Про велике від". Нижче для порядку я наведу суворе визначення, але практично потрібно лише вказати порядок швидкості зростання часу роботи алгоритму у разі зростання основного параметра завдання. p align="justify"> Коефіцієнт перед функцією від N не важливий: якщо потрібна N^2 дія або 100 * N^2 дій - це все одно буде O(N^2), тому що в обох випадках зростання N в два рази збільшує час роботи в чотири.

"O"-позначення використовується, якщо потрібно визначити верхню асимптотичну межу для функції f(n), рівну часу роботи алгоритму в залежності від основного параметра задачі.

Визначення взято з книги Томаса Кормена "Алгоритми. Побудова та аналіз". Для цієї функції g(n) позначення O(g(n)) означає безліч функцій O(g(n)) = =n0>

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

Програмісти не слідують педантично строгому визначенню і спрощують приблизно таке: f(n) = O(g(n)), якщо функція f(n) при великих n поводиться пропорційно функції g(n).

Насправді найчастіше зустрічаються п'ять функцій визначальних складність алгоритму:

O(1) Константа. Час роботи фіксований і залежить від розміру завдання. O(log(n)) Логарифм. Основа логарифму опускається, оскільки перехід від однієї підстави до іншого це множення на константу. O(n) Лінійна складність. Час зростає пропорційно до розміру завдання. O(n*log(n)) Складність, що називається "Ен лог ен". Усі добрі алгоритми сортування мають таку складність. O(n*n) Квадратична складність. Наприклад, всілякі попарні операції у масивах.

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

Java розробнику бажано знати кілька основних алгоритмів, розуміти їх складність та сферу застосування. Вони зібрані у таблиці нижче.

Декілька слів про алгоритм швидкого сортування (QuickSort). Сам алгоритм добре описано тут.Алгоритм має пару нюансів розуміння та реалізації, без яких його продуктивність може падати до O(n^2), і алгоритм стає цікавим лише в академічних цілях, але не в практичних.

1. Як опорний елемент повинен вибиратися випадковий елемент. Лівий, правий чи середній – не підходять. Тоді в середньому довжина більшої частини масиву буде втричі більшою за меншу (співвідношення три до одного). Тобто гірше, ніж розбиття точно навпіл, але довжина ланцюжка рекурсивних викликів все одно буде логарифмом. Імовірність на кожній ітерації випадково потрапляти в максимальний або мінімальний елемент дуже мала (приблизно 0.001^1000 для масиву з тисячі елементів). У разі навіть гірший час роботи теж буде O(nlog(n)), а чи не O(n^2), як заведено говорити. Хоча це суто моя думка, зазвичай кажуть, що теоретично може бути квадратична складність, але на практиці дуже рідко.
2. Слід вибирати версію алгоритму, яка ділить підмасив на три частини: менші за опорні, рівні йому, і більші. Класичне визначення алгоритму розбиває на частини: менші чи рівні й великі, та заодно робиться припущення, що це елементи різні. Якщо знехтувати цією деталлю і застосувати класичну реалізацію масиву рівних елементів, то отримаємо складність O(n^2). Тобто найдовше алгоритм працює коли і робити нічого не потрібно! Якщо виділити елементи, рівні опорному в окрему групу, то для масивів з елементами, що повторюються, навпаки отримаємо суттєвий виграш.

У реальних додатках з якістю коду нижче за середній можна зустріти неефективну реалізацію типових завдань. Наприклад, перетин двох колекцій можна порахувати за O(n), скопіювавши дані в HashSet, а насправді використовується повний попарний перебір за O(n^2). Або ми шукаємо дані у списку багато разів за O(n), хоча можна відсортувати його один раз або ж використовувати TreeSet і тоді скористатися бінарним пошуком за O(log(n)).

Розберу одне завдання із типових питань із співбесід. Постановка завдання така: видалити елементи з непарними номерами зі списку, тобто кожен другий елемент. На stackoverflow є сторінка зі схожим питанням, хоч і стара і з невеликою кількістю коментарів. Але відповіді, які пропонуються як рішення, досить показові. Код GitHub.

На жаль, у питанні спочатку уточнюється, що видалити потрібно з ArrayList ("Remove odd elements from ArrayList while iterating"). Ми знаємо, що видалення елемента ArrayList призведе до копіювання всієї хвостової частини, тобто коштуватиме O(n), тому сумарна складність буде O(n^2). Розумно ж очікувати, що видалення буде зроблено за один прохід за списком, тобто O(n), і це легко досягається для LinkedList. Тому спочатку використання ArrayList для такого сценарію неправильне. Якщо ми зав'язані на ArrayList, то в реальному додатку варто зробити копію масиву і потім оновити посилання. Якщо і це не застосовно, то можна написати складний код, який копіюватиме елементи на порожні місця, а потім видалить хвіст, але все-таки завершиться за один прохід масивом.

Працювати зі списком індексів елементів неприродно. Зазвичай предикат залежатиме від самих елементів списку, і тоді рішення було б таким:

//java8
elements.removeIf(s
->
Long.parseLong(s)
%
2
==
1);

//before java8
for
(IteratorString>
iterator
=
elements.iterator();
iterator.hasNext();
)

String
next
=
iterator.next();
if(Long.parseLong(next)
%
2
==
1)

iterator.remove();
>
>

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

//java8
AtomicInteger
counter
=
new
AtomicInteger(0);
elements.removeIf(s
->
counter.incrementAndGet()
%
2
==
0);

//before java8
int
counter
=
0;
for
(IteratorString>
iterator
=
elements.iterator();
iterator.hasNext();
)

iterator.next();
if
(counter++
%
2
==
1)

iterator.remove();
>
>

//before java8
//хитрий спосіб уникнути введення змінної counter.Слід уникати таких неочевидних прийомів.
for
(ListIteratorString>
literator
=
elements.listIterator(elements.size());
literator.hasPrevious();)

literator.previous();
if
(literator.previousIndex()
%
2
==
0)

literator.remove();
>
>

//O(n) for ArrayList
//Рішення на крайній випадок, якщо можливі проблеми з продуктивністю, але від ArrayList не втекти.
//обсяг коду не відповідає складності завдання, його читання теж низька, доведеться пояснювати в коментарях,
/ / Чому так, а не інакше
//якщо застосувати це рішення до LinkedList, то отримаємо O(n^2)
removeFromArrayList(elements,
i
->
i
%
2
==
1);
static
void
removeFromArrayList(ArrayListString>
elements,
IntPredicate
removeIf)

int
lastIndex
=
0;
for
(int
i
=
0;
i

elements.size();
i++)

if
(!removeIf.test(i))

elements.set(lastIndex,
elements.get(i));
lastIndex++;
>
>
int
extraElementsCount
=
elements.size()
-
lastIndex;
//unfortunately, we can't use protected removeRange method
for
(int
i
=
0;
i

extraElementsCount;
i++)

elements.remove(elements.size()
-
1);
>
>

Прокоментую рішення, запропоновані на stackoverflow.

//1.
/ / Коректне рішення. O(n^2) для ArrayList, O(n) для LinkedList
int
i
=
0;
for
(IteratorString>
it
=
words.iterator();
it.hasNext();
)

it.next();
// Add this line in your code
if
(i
%
2
!=
0)

it.remove();
>
i++;
>

//2.
//Некоректне рішення. O(n^2) для ArrayList, O(n^2) для LinkedList.
//Помилковий результат при дублюючих значеннях у списку.
int
i
=
0;
ListString>
list
=
new
ArrayListString>();
for
(String
word:words)

if
(i
%
2
!=
0)

//it.remove();
list.add(слово);
>
i++;
>
words.removeAll(list);
// Елементи видаляються за значенням!
//Додумати рішення можна так (ще замінити умову на ==0):
//words.clear();
//words.addAll(list);

//3.
//На цьому прикладі я зазнав фіаско. Я був упевнений, що код не працює, тому що розмір та індекси будуть змінюватися по ходу роботи алгоритму,
//що видаляючи елемент з індексом 2, ми видаляємо елемент з індексом 3 у вихідному масиві. Все переплуталося і не може дати правильного результату.
//Але! результат правильний.На кожному кроці ми видаляємо елемент, зрушуємо всі індекси на 1 вліво, але збільшуємо лічильник на 1, а чи не на 2.
//тут мої повноваження все, як кажуть
//Складність O(n^2) для ArrayList та LinkedList
int
i
=
1;
while
(i

words.size())

words.remove(i++);
>

//4.
/ / Коректне рішення. Єдине із запропонованих O(n) для ArrayList; O(n^2) для LinkedList.
//Мінус - код, що важко читається. Два лічильники називаються i, j. Причому j завжди дорівнює i/2.
//Якщо це не Ви писали, то доведеться запускати налагодження, щоб розібратися.
int
j
=
0;
for(int
i
=
0
;
i

integers.size();
i++) if(
i
%
2
==
0) integers.set(j,
integers.get(i));
j++;
>
>
int
half
=
integers.size()%2==0
?
integers.size()/2
:
integers.size()/2
+
1;
integers.subList(half
,
integers.size()).clear();//знатиму, що subList не створює новий список, а лише посилання на підсписок поточного.
/ / Тому хвіст можна обрізати ось так в один рядок.

Приклад з видаленням один із самих базових і простих. Подібним чином можна мусолити будь-які колекції та операції з ними: LinkedList, ArrayList, HashMap, TreeMap, LinkedHashMap, CopyOnWriteArrayList і таке інше. У цьому пості я цього робити не буду, перейду до підсумку всього, що я тут написав.

Висновок

Доводиться дотримуватися тонкого балансу між оптимальністю рішення щодо продуктивності, читальністю та лаконічністю коду та здоровим глуздом. Головне розуміти наскільки швидко можна вирішити типове завдання та підібрати правильні структури даних та операції з ними. На інтерв'ю на позицію Java розробника часто питання з цієї тематики буде другим (після " методів класу Object " чи " розкажіть про останній проект " ).