Розглянемо поняття складності  алгоритму

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

• дані з вимірювальних пристроїв, що неперервно надходять, наприклад, з датчиків, що визначають стан ядерного реактора;

• дані від сотень мільйонів користувачів соціальних мереж;

• дані з метеорологічних станцій, що розташовані в багатьох точках Земної кулі;

• дані від користувачів мереж мобільного зв'язку; та багато інших.

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

Швидкість роботи алгоритму визначається його складністю.

Складність алгоритму - це комплексна властивість алгоритму, яка визначає:

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

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

Часова та ємнісна складність алгоритму тісно пов'язані між собою i кожна з них залежить від обсягу вхідних даних.

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

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

Якщо алгоритм містить цикли, але не містить вкладені цикли, то час виконання такого алгоритму пропорційний деякій константі, помноженій на кількість вхідних даних n, оскільки від кількості даних залежить кількість повторів команд циклу. Складність такого алгоритму називається лінійною i позначається О(п). Це означає, що якщо кількість вхідних даних збільшити, наприклад, у 5 разів, то час виконання алгоритму теж збільшиться в 5 разів. Такими алгоритмами є, наприклад, алгоритм для обчислення суми всіх елементів одновимірного масиву з n елементів aбo алгоритм знаходження значення найбільшого елемента такого масиву. У таких алгоритмах вхідні дані переглядаються тільки 1 раз.

Якщо алгоритм містить вкладені один в інший два цикли, то час виконання такого алгоритму пропорційний деякій константі, помноженій на квадрат кількості вхідних даних n2. Складність такого алгоритму називається квадратичною i позначається О(п2). Це означає, що якщо кількість вхідних даних збільшити, наприклад 5 разів, то час виконання алгоритму збільшиться в 52=25 разів. Такими алгоритмами є, наприклад, розглянуті в цьому пункті алгоритми впорядкування одновимірного масиву з n елементів. У таких алгоритмах вхідні дані переглядаються приблизно n2 разів.

Якщо алгоритм містить вкладені один в інший три цикли, то час виконання такого алгоритму пропорційний деякій константі, помноженій на куб кількості вхідних даних n3. Складність такого алгоритму називається кубічною i позначається О(п3). Це означає, що якщо кількість вхідних даних збільшити, наприклад, у 5 разів, то час виконання алгоритму збільшиться в 53=125 разів. У таких алгоритмах вхідні дані переглядаються приблизно n3 разів.

Лінійна, квадратична, кубічна складності є частковими випадками поліноміальної складності, яка позначається O(nт), де m - натуральне число.

Розрізняють ще й інші види складності алгоритмів.

3 поняттям складності алгоритму безпосередньо пов'язано поняття його ефективності. Алгоритм, який виконується швидше i/або використовує менший об'єм пам'яті, вважається ефективнішим. 

Тому чим менша складність алгоритму, тим він ефективніший.

Ефективність алгоритму може залежати від набору вхідних даних. Так якщо порівняти розглянуті алгоритми впорядкування одновимірних масивів з n елементів, то з'ясується, що для невеликої кількості елементів (n<100) швидше виконується алгоритм впорядкування методом обміну, а для (n>100) - алгоритм впорядкування методом вибору.

Для розв'язування однієї й тієї ж задачі можна скласти алгоритм різної складності, а значить й різної ефективності. Розглянемо одну таку задачу.

Задача. Дано впорядкований за зростанням одновимірний масив з n елементів i ще одне число. Визначити, чи є це число серед елементів масиву.

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

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

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

Цей алгоритм називається алгоритмом половинного поділу. Він був відомий ще стародавнім грекам i називався дихотомією.

Якщо порівняти ефективності алгоритму послідовного перегляду i алгоритм половинного поділу, то при n = 1000  в першому алгоритмі потрібно виконати максимум 1000 порівнянь, а в другому - максимум 10.