Алгоритми та структури даних — від «десь чув» до «ефективно застосовую»

«Алгоритми...? Структури даних...? Хм... Десь таке колись чув, але це щось незрозуміле, застаріле і дуже важке для розуміння. Вчити все це — марна трата часу. Мені це точно ніколи не знадобиться, бо у мене потужний комп’ютер і я пишу виключно на сучасних мовах програмування в яких взагалі не потрібні такі знання!»

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

Мене звати Євген Радченко, зараз я займаю позицію Lead SAP Software Engineer у Німеччині. Саме знання алгоритмів і структур даних допомагають мені думати алгоритмами і писати ефективний код. Але подібні висловлювання про алгоритми, як наведені вище, я все частіше чую як від початківців чи студентів, які мріють стати програмістами, так і від колег, які вже мають великий комерційний досвід. При чому обманюються у ставленні до алгоритмів як наші земляки, так і колеги з усього світу, з якими мені доводилось працювати на міжнародних проєктах.

Це говорить про глобальну проблему: алгоритми і структури даних недооцінюють та їх освоєнню виділяється замало часу.

Скоріш за все, в університеті чи на курсах буде зроблений акцент на конкретній мові програмування, її синтаксисі та можливостях. Після цього студент, може закривати якісь задачі, використовуючи стандартні можливості мови, але не маючи гадки, чому воно працює саме так і чи можна якось суттєво покращити якість коду. Більшість з досвідом покращують лише свої навички у мові програмування, використовуючи сучасні «фічі» та збільшуючи їх кількість, але, на жаль, це не є «gamechanger». Щоб дійсно суттєво покращити ефективність коду, потрібно розуміти, скажімо, як прискорити виконання логіки чи позбутись зайвого використання пам’яті.

Спробую пояснити, чому я вважаю, що знання алгоритмів та структур даних необхідні всім програмістам та значно посилюють їх як спеціалістів; які саме алгоритми бувають і як їх ефективно використовувати. У статті зібрана детальна інформація про всі основні складності та структури даних з використанням алгоритмів. Буде багато цікавого матеріалу, пояснень та прикладів коду. Також будуть завдання, на яких можна потренуватися, щоб закріпити вивчене.

Добрий ранок, добрий день, добрий вечір, доброї ночі! Я вітаю кожного! Ми починаємо, поїхали!

Для кого написана ця стаття

Якщо ти взагалі не тямиш нічого у програмуванні і хочеш з чогось почати, але не знаєш з чого саме, то інформація, яку ти тут отримаєш, стане гарним «entry point» у світ розробки.

Якщо ти навчаєшся та мрієш стати хорошим програмістом, то матеріал який буде освітлено — саме для тебе.

Якщо ти вже хороший програміст та хочеш стати ще кращим, то теми, які будуть розкриті, стануть тобі у пригоді.

Якщо ти вже senior-помідор, гуру програмування та пізнав «дзен», то бери свою каву, сідай зручніше та перевір, чи ще не заіржавів і пам’ятаєш ази.

Якщо ти готуєшся до співбесіди у топ компанію — цей матеріал допоможе тобі у підготовці.

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

Якщо ти хочеш розв’язувати дійсно важкі та цікаві задачі, де надійність і продуктивність являються ключовими — написане саме для тебе.

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

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

Тож ти можеш робити все те саме, але використовувати комфортну мову програмування замість запропонованої.

Для чого і що це взагалі

«Алгоритми служать базовими елементами будь-якої машинної програми. В організації структур даних і процедур їх обробки закладена можливість перевірки правильності роботи програми.»

Ніколас Вірт, автор мови програмування Паскаль.

Ти зараз скажеш щось типу: «У наші дні дуже потужні машини, які „витягнуть“ все, і я не повинен заморочуватися з цими алгоритмами.»

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

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

Наведу приклад з особистого досвіду: раптово у продуктивній системі перестав працювати один дуже важливий функціонал, який був реалізований багато років тому (більш як 10) і який використовується замовниками компанії по всьому світу кожного дня. До цього часу все працювало, як швейцарський годинник, і ніхто у цю частину коду з того часу не заглядав. Компанія почала втрачати величезні гроші кожну хвилину, а найстрашніше — репутацію та клієнтів. «Backup» не допоміг.

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

Я переробив проблемну частину і після змін все запрацювало знову, щобільше, користувачі відмітили, що функціонал став набагато «user friendly» (з точки зору відгуку на їх дії) і вони тепер можуть швидше працювати.

Важливо наголосити: у користувачів були надсучасні та потужні машини — ноутбуки, планшети, смартфони. З боку компанії так само — найкрутіша база даних, надпотужні сервери. Але все це ніяк не допомогло, бо логіка обробки була неефективна. Проблемі можливо було запобігти з самого початку, 10+ років тому, написавши ефективний код, який би однаково швидко працював, як тоді на старих, так і зараз на сучасних машинах.

Програміст не мислив алгоритмічно та не думав про наслідки. Припущу, що навіть не здогадувався, що робить щось не так, і не знав, чи є варіант зробити суттєво краще.

Будемо вважати, розібрались для чого це, а тепер переходимо до питання «Що це?».

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

Наприклад, я маю декілька підручників, які кожен день потрібно носити з собою. Це мої дані. Також маю вдома, скажімо: рюкзак, валізу для подорожей на коліщатках та дерев’яний ящик. Це мої структури даних. 100% не виберу дерев’яний ящик, бо він важкий і великий. Буду витрачати багато зусиль, до того ж стану значно повільнішим. Мені такий варіант не підходить. Далі, маю дорожню валізу, вона вже виглядає не так страшно, але все одно, заради декількох підручників не буду кожен день їздити з нею. Це не зручно і, знову ж таки, витрачається зайвий час та сили, щоб впоратись з нею. І от, нарешті, рюкзак, який підходить ідеально та вирішує мою проблему ефективно. З ним я стаю мобільний, не витрачаю зайвий час та сили, обидві руки вільні.

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

Як же все зміниться, якщо мої дані — не пара підручників, а, скажімо, одяг для зимового відпочинку, і мені не потрібно носити його з собою кожен день. Тільки перевезти речі від дому до готелю і назад. Рюкзак не підходить, бо замалий, і не всі потрібні речі помістяться, а про ящик взагалі мовчу. Звісно, буду радий дорожній валізі. А от якщо мені потрібно десь у підвалі зберігати будівельний інструмент, який дуже рідко дістаю, то дерев’яний ящик стане у пригоді. Це практично, і з ним нічого не станеться через десятки років, його неможливо зіпсувати інструментами — чого не скажеш про рюкзак чи валізу.

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

Тому дуже важливо для програміста знати їх усі та, розуміючи умови задачі, обрати правильну. Щоб не бути схожим на того, хто кожен день носить підручники у валізі чи їде у подорож з речами у дерев’яному ящику =)

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

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

Складність алгоритму та Big O

Це дуже важлива тема, тому присвячу багато часу цьому розділу. Багато хто плутається у розумінні цих понять, але я спробую пояснити просто і на прикладах. У кінці розділу перевіримо знання та потренуємося.

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

В обох випадках складність залежить від вхідних даних: список з 10 клієнтів відпрацює швидше та займе менший обсяг пам’яті, ніж аналогічний зі 100 000. При чому точний час нікого не цікавить: це залежить від мови програмування, типу даних, процесора та багато іншого. Важлива лише складність при прагненні розміру вхідних даних до нескінченності (асимптотична складність) — тобто, як буде зростати витрата ресурсів (часу та пам’яті) зі збільшенням вхідних даних.

Стежити за зростанням і у порівнянні витрати ресурсів допоможе поняття «Big O» (О-нотація, як її називають). О прийшла в IT-світ з математики, але я на цьому зараз не зупинятимуся. Для нас достатньо сказати, що Big O — це описання верхньої можливої межі. Зараз на прикладі поясню, що це означає.

Спершу поговоримо про час (Time Complexity, чи просто TC)

Наприклад, є int масив, який має N елементів. Алгоритм друку усіх значень масиву буде мати складність алгоритму O(N), тому що потрібно перевірити кожен елемент масиву. Кількість елементів масиву = кількість ітерацій у циклі. Якщо 10 елементів, то 10 ітерацій — якщо 100 000, то 100 000.

void printArray(vector<int> arr)
{
	for(int i = 0; i < arr.size(); ++i)
    	cout << arr[i] << endl;
}

У цьому прикладі, ми точно знаємо, що складність не зміниться і завжди буде O(N), тому що неможливо перевірити усі елементи масиву зробивши менше ітерацій. Чого не можна сказати про наступний приклад:

Маємо той самий масив, але нам потрібно друкувати до тих пір, поки ми не зустрінемо цільове значення, яке передане параметром.

void printArrayUntilGoal(vector<int> arr, int goal)
{
	for(int i = 0; i < arr.size(); ++i)
	{
    	cout << arr[i] << endl;
    	if(arr[i] == goal) return;
	}
}

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

Але ми чітко можемо сказати, що складність алгоритму не перевищить O(N), хоча менше — цілком можливо.

Ось ця максимально можлива межа і є Big O. Це дуже схоже на відношення «менше або дорівнює» (<=). Якщо я маю 100 гривень у гаманці, то можу витратити менше або рівно 100, але ніяк не більше.

Переходимо до пам’яті (Space Complexity, чи просто SC)

Кожен гарний програміст повинен дбати про обсяг витраченої пам’яті чи простору. Просторова складність є паралельним поняттям часовій складності. Тобто, з одного боку існує верхня межа часу — TC, а з іншого верхня межа простору — SC. Потрібно думати про обидві складності одночасно.

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

Таких прикладів може бути дуже багато, але візьмемо за правило, що завжди потрібно піклуватись про TC & SC однаково, і намагатись максимально оптимізувати, якщо немає ніяких додаткових обставин.

Поглянемо на перший приклад — O(N) TC. Що ми можемо сказати про SC? Чи витрачається додатковий простір? Ні, бо логіка «бігає» по вхідному масиву. Тому можна сказати так: даний алгоритм має O(1) SC. О(1) використовується для опису константної складності алгоритму.

Зараз буде те, що дуже часто бачу у реальних алгоритмах:

void printArray(vector<int> arr)
{
    vector<int> a = arr;
	for(int i = 0; i < a.size(); ++i)
    	cout << a[i] << endl;
}

Створюється новий масив, такого ж самого розміру, як і вхідний, та копіюються всі дані. На результат цей «move» ніяк не вплине.

Що тепер з Big O:

TC — O(N), як і раніше, бо алгоритму не має різниці, яким саме масивом «ходити». Оскільки розмір масиву не змінився — кількість ітерацій залишається такою ж.

SC — стало O(N), а було О(1) (не враховую вхідний масив, бо ми ніяк на це повпливати не можемо). Створена копія вхідного масиву і для неї виділено такий самий обсяг пам’яті. Тобто, ми зробили гірше, витрачаючи додатковий ресурс, і алгоритм тепер менш ефективний. Чи була якась необхідність у виділенні додаткового простору? Ні.

Дуже часто кожен програміст пише щось подібне, не задумуючись, як це впливає на витрату ресурсів. «Працює — от і добре, значить, я молодець і все правильно зробив! Юхуууу». Але важливо ретельно планувати логіку та перевіряти код після написання, за можливості, позбуваючись зайвого.

Далі поговоримо про те, які Big O бувають, яка між ними різниця та як їх порівнювати.

О(1) — Константна складність (Constant)

Алгоритм має О(1) складність — коли відомо, скільки точно разів щось відбудеться, чи скільки пам’яті буде виділено, незалежно від зміни вхідних даних. Тобто, алгоритм завжди буде використовувати однакову кількість ресурсів. Це найкраща можлива складність, до якої потрібно прагнути.

З малюванням у мене не дуже, заздалегідь перепрошую за усі наступні ілюстрації, але «Батя я стараюсь» =)

Подивимось на декілька прикладів.

Приклад № 1:

int n = 100;
for(int i = 1; i <= n; ++i)
	cout << i << endl;

Алгоритм друкує числа від 1 до 100. Складність TC і SC — О(1), тому що ми точно знаємо, скільки ітерацій потрібно (100) та скільки пам’яті буде виділено. У С++ int змінна завжди займає 4 байти, в нашому прикладі 2 змінні (n та і), які потребують 4+4 = 8 байтів. Ми знаємо точну кількість тому й О(1).

Приклад № 2:

vector<int> a = {1,2,3,4,5};
for(int i = 0; i < a.size(); ++i)
	cout << a[i] << endl;

Алгоритм друкує всі елементи масиву. Відомо, що у масиві 5 елементів, тож цикл виконається рівно 5 разів, а значить О(1) TC. Оскільки відома кількість елементів і тип, то можемо порахувати, скільки пам’яті знадобиться — 5 (ел. масиву) * 4 (байти за кожен) + 4 (байти за i) = 24 байти. Знаючи точну кількість простору, можна впевнено сказати — О(1) SC. Далі я не буду у кожному прикладі рахувати пам’ять — принцип підрахунку незмінний, і у тебе є змога потренуватись.

До речі, ти можеш спитати: «Жека, зачекай, але ж доступ до масиву чогось вартує?». Мій тобі персональний «лайк», якщо ти задумався над таким питанням. Відповідаю: звісно, вартує, але доступ до будь-якого елементу масиву має О(1) складність, про яку ти читаєш прямо зараз. Це можливо завдяки властивості цієї структури даних — детальніше описую у розділі про масиви, залітай!

Цілком ймовірно, що не константна складність буде швидшою за константну.

Наприклад, О(N), про який піде мова далі у розділі, швидше ніж О(1). Скомбінуємо декілька попередніх прикладів:

void printArray(vector<int> arr)
{
	vector<int> a = {1,2,3,4,5};
	for(int i = 0; i < a.size(); ++i)
    	cout << a[i] << endl;
 
	for(int i = 0; i < arr.size(); ++i)
    	cout << arr[i] << endl;
}

ʼaʼ — завжди має 5 елементів. ʼarrʼ може бути порожній, мати менш як 5, або набагато більше. Через те, що не відома довжина ʼarrʼ цей алгоритм не є О(1), а O(N) де N — довжина ʼarrʼ. Поки відома довжина, то немає різниці наскільки ʼаʼ великий (100 чи 10000000 елементів) — ʼarrʼ може бути ще більше і «рости» швидше, наздогнавши та обігнавши константу рано чи пізно:

З цього витікає правило — константні величини відкидаються, незважаючи наскільки вони великі, тому що на прагнення до нескінченності це суттєво не вплине.

О(N) — Лінійна складність (Linear)

У попередніх прикладах нам вже довелось зіткнутись з цією складністю. Тут все доволі зрозуміло:

TC — кількість ітерацій = кількість елементів.

SC — якщо потрібно створити масив з N елементів, то це буде O(N) SC.

Приклад:

На вхід дається масив чисел. Знаючи заздалегідь, що кожне число не менше 0, та не більше 100. Потрібно знайти і надрукувати мінімальне та максимальне значення:

void findMinMax(vector<int> arr)
{
	int min = 101; // Знаючи з умови, що 100 може бути максимум
	int max = -1; // Знаючи, що 0 мінімум
 
	for(int i = 0; i < arr.size(); ++i)
	{
    	if(arr[i] < min) min = arr[i];
    	if(arr[i] > max) max = arr[i];
	}
	cout << "Min - " << min << endl;
	cout << "Max - " << max << endl;
}

TC — O(N), тому що кількість ітерацій залежить від розміру ‘arr’.

SC — O(1), тому що створили лише декілька змінних і відомо, скільки потрібно пам’яті.

Порівняємо з прикладом, алгоритм якого робить все те ж саме, але по-іншому:

void findMinMax(vector<int> arr)
{
	int min = 101;
	int max = -1;
 
	for(int i : arr)
    	if(i < min) min = i;
 
	for(int i : arr)
    	if(i > max) max = i;
	
	cout << "Min - " << min << endl;
	cout << "Max - " << max << endl;
}

TC — O(N+N) = O(2N), через 2 цикли. Але пам’ятаємо правило, що константу завжди відкидаємо. Тому складність — O(N).

SC — O(1) без змін.

О(log N) — Логарифмічна складність (Logarithmic)

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

Я спочатку наведу дуже простий приклад з реального життя, а потім поясню, що означає магічне «log» і звідки воно береться.

Уяви, що пʼєш вдома каву з товаришем, і на столі лежить торт «Наполеон» довжиною 16 см. Спочатку ріжеш його навпіл — зʼїли половину. Залишилось 8 см. Знову ріжеш навпіл — зʼїли. Залишилось 4. І так продовжуєш до кінця:

N = 16 — [----------------]
N = 8 — [--------]
N = 4 — [----]
N = 2 — [—]
N = 1 — [-]

Хтось один доїсть 1 см торта, бо далі різати не вийде.

Скільки разів довелося різати торт? — 4 рази.

Можливо поставити запитання — скільки разів потрібно 1 помножити на 2, щоб отримати 16 (або N в загальному випадку)?

N = 1
N = 2 (N*2 => 1*2)
N = 4 (N*2 => 2*2)
N = 8 (N*2 => 4*2)
N = 16 (N*2 => 8*2)

Маємо таку формулу — 2^k = N, де k — кількість розрізів.

Це саме те, що у математиці виражає log:

log₂N = k ⇔ 2^k = N

У нашому випадку:

log₂16 = 4 ⇔ 2⁴ = 16

Коли говорять про складність алгоритму, то основу логарифма опускають — O(log N). Основа не має значення для цілей «Big O».

Багато алгоритмів мають логарифмічну складність — бінарний пошук (Binary Search), пошук у збалансованому бінарному дереві пошуку (Balanced Binary Search Tree), та багатьох інших. Причиною цього є його ефективність, яка набагато краще ніж О(N).

Приклад:

Маємо 1000 елементів масиву — для О(N) це 1000 ітерацій, а для О(log N) потрібно лише 9 (насправді 9.9657, але залишаємо лише цілу частину).

Простий «lifehack», як зрозуміти, що алгоритм має O(logN) — коли на кожному кроці кількість елементів зменшується вдвічі, то це скоріш за все O(log N).

Багатокомпонентні алгоритми: додавання чи множення

Звичайна справа, коли алгоритм має декілька кроків та необхідно порахувати складність. Розглянемо декілька прикладів.

Приклад № 1:

void findMinMax(vector<int> arr)
{
	for(int i : arr)
    	cout << i << endl;
	…
	for(int i : arr)
    	cout << i << endl;
}

TC — O(N), де N довжина arr. Взагалі то О(N+N) = O(2N), але памʼятаємо, що константу не враховуємо.

Приклад № 2:

void printArray(vector<int> arr)
{
	for(int i : arr)
	{
    	for(int j : arr)
    	{
            cout << i*j << endl;
    	}
	}
}

Або коротше:

void printArray(vector<int> arr)
{
	for(int i : arr)
    	for(int j : arr)
            cout << i*j << endl;
}

Що з TC? Вже не два поодинокі цикли, а один вкладений в інший. Тому мусимо не додавати, а множити.

ТС — О(N*N) = O(N²).

Приклад № 3:

void printArray(vector<int> arr)
{
	for(int i : arr)
    	for(int j : arr)
            cout << i*j << endl;
	…
	for(int i : arr)
    	cout << i << endl;
}

У прикладі № 3 скомбіновані два попередні.

ТС — O(N²) + O(N).

Вступає в силу нове правило, яке дуже схоже на попереднє з відкиданням констант.

Відкидаємо усі не домінуючі умови. Вважаємо їх такими самими константами. O(N²) + O(N) => O(N²) — відкидаємо O(N) тому, що не буде мати значної різниці у зростанні на фоні домінуючого O(N²).

Це правило діє лише дня одного набору вхідних даних.

Приклад № 4:

void print2Arrays(vector<int> arr1, vector<int> arr2)
{
	for(int i : arr1)
    	cout << i << endl;
 
	for(int i : arr2)
    	cout << i << endl;
}

TC — (N + M), де N — довжина arr1, а M — довжина arr2.

Як результат — надрукуються спочатку елементи arr1, а потім arr2. Якщо arr1 має 5 елементів, а arr2 має 10 елементів, то загальна кількість ітерацій буде 5+10 = 15.

Приклад № 5:

void print2Arrays(vector<int> arr1, vector<int> arr2)
{
	for(int i : arr1)
    	for(int j : arr2)
            cout << i+j << endl;
}

TC — (N * M), де N — довжина arr1, а M — довжина arr2.

Як результат — кожен елемент з arr1 буде доданий до кожного елементу arr2, та буде надрукована сума. Якщо arr1 має 5 елементів, а arr2 має 10 елементів, то загальна кількість ітерацій буде 5*10 = 50.

У прикладах 4 та 5 нічого не відомо про довжину вхідних масивів — це не константи. Також обидва можуть мати дуже різні розміри, а значить — нічого не можливо скоротити чи позбутися.

Простими словами, як зрозуміти, коли додавання, а коли множення:

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

Перевір себе, яка буде складність:

• O(N² + N) — (відповідь — O(N²))
• O(N² + N²) — (відповідь — O(N²))
• O(N + log N) — (відповідь — O(N))
• O(17567N + N + N²) — (відповідь — O(N²))
• O(N + log M) — (відповідь — O(N + log M))
• O(N² + M²) — (відповідь — O(N² + M²))
• O(44N + 52N + log N + 8M + log M) — (відповідь — O(N + M))

void print2Arrays(vector<int> arr1, vector<int> arr2)
{
      	for(int i : arr1)
      		for(int j : arr1)
               	cout << i+j << endl;
 
    	 for(int i : arr2)
      		for(int j : arr2)
               	cout << i+j << endl;
}

(відповідь — O(N² + M²))

void printArray(vector<int> arr)
{
	vector<int> a = {1,2,3,4,5};
	for(int i = 0; i < a.size(); ++i)
	    for(int j = 0; j < arr.size(); ++j)
                cout << a[i]+arr[j] << endl;
}

(відповідь — O(5N)=>O(N))

О(N²) — Квадратична складність (Quadratic)

Вже багато було сказано про цю складність. Підсумую на прикладі: якщо вхідний масив має 5 елементів, то ітерацій буде 25 (5*5). Це популярна складність для деяких алгоритмів сортування та класична при роботі з матрицею (двовимірний масив, про який ми поговоримо детально у розділі про масиви).

Також цілком можливі складності — O(N³), O(N⁴), ... , O(N^N). На них я зараз зупинятись не буду, бо вони схожі, але відрізняються лише швидкістю зростання та зустрічаються рідше.

О(NlogN) — Лінійно-логарифмічна складність (Linearithmic)

Ця складність трошки повільніша за лінійну, але значно швидша за квадратичну. Застосовується переважно в ефективних алгоритмах сортування — злиттям (Mergesort), швидке сортування (Quicksort), інші. Звідки зʼявляється logN і що це таке — читай вище у підрозділі про логарифмічну складність.

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

1. Розділяємо масив навпіл до тих пір, поки не залишиться по 1 чи 0 елементів у кожному.
2. Зливаємо в один масив з двох вже відсортованих підмасивів, порівнюючи елементи по черзі.

Розберемося звідки береться складність:

Розділяємо

| 6 5 3 1 8 7 2 4 |
| 6 5 3 1 | 8 7 2 4 |
| 6 5 | 3 1 | 8 7 | 2 4 |
| 6 | 5 | 3 | 1 | 8 | 7 | 2 | 4 |

Зливаємо

| 5 6 | 1 3 | 7 8 | 2 4 |
| 1 3 5 6 | 2 4 7 8 |
| 1 2 3 4 5 6 7 8 |

N — кількість елементів (у нашому випадку — 8). На кожному рівні завжди однакова кількість елементів, для яких необхідна логіка злиття. Злиття потребує O(N), щоб порівняти усі елементи. Подивимося на кількість рівнів — їх буде стільки скільки разів N можливо поділити на 2 (у нашому випадку — 3). Це якраз і є logN = 3. Тож маємо O(NlogN) TC, але SC — O(N), бо у кінці буде створено масив для злиття такою ж самою довжиною, як і вхідний масив.

O(2^N) — Експоненціальна складність (Exponential)

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

Приклад:

int exp(int n)
{
	if (n <= 1) return 1;
	return exp(n - 1) + exp(n - 1);
}

Побачивши ‘exp(n — 1) + exp(n — 1)’, багато хто скаже — квадратична складність чи лінійна(N+N = 2N = N), але це взагалі не правильне твердження.

Ми можемо дуже просто порахувати кількість викликів самотужки. Нехай N = 4, тоді:

Дерево викликів має глибину N. На кожному рівні викликається функція ‘exp’ рівно 2 рази. Маємо O(2^N).

Важливо запамʼятати цей патерн — часто (але не завжди), коли функція викликає сама себе декілька разів, має складність O (кількістьВикликівФункції^{глибина(кількістьРівнів)}).

Це призводить до загального випадку — O(C^N). C — будь-яке число (кількість викликів), N — кількість рівнів.

Прикладом може бути такий алгоритм:

void exp(int n, int c)
{
	if (n <= 1) return 1;
	for(int i = 1; i <= c; ++i)
     	exp(n – 1, c);
}

O(N!) — Факторіальна складність (Factorial)

Факторіал — це множення усіх цілих чисел, більших за 0 та не перевищуючих самих себе.

Наприклад: 5! = 5*4*3*2*1 = 120.

Як можна здогадатися — дуже стрімко зростає.

Деякі специфічні алгоритми застосовують дану складність. Прикладом може бути задача з перестановкою string усіма можливими способами:

‘a’ => [‘a’]
‘ab’ => [‘ab’, ‘ba’]
‘abc’ => [‘abc’, ‘acb’, ‘bac’, ‘bca’, ‘cab’, ‘cba’]

Наразі достатньо розуміти, що алгоритми з даною складністю набагато повільніші за усі інші (окрім O(N^N)), які обговорювались.

Також є багато інших складностей, наприклад (O(2^N*N!)), які ще повільніші. Їх всі пам’ятати не потрібно, лише розуміти, який швидший. Твоя задача — завжди намагатися використати алгоритм зі швидшою складністю, але, звісно, бувають специфічні алгоритми, які потребують конкретних складностей, навіть найповільніших.

Big O — важкий на початку, але маючи базові знання та практикуючись на різних задачах, — розуміння приходить. З досвідом ті самі підходи будуть з’являтися знову і знову, на «автоматі» будеш вибирати, який алгоритм застосувати і чому саме він підходить.

Усі складності, про які йшла мова у розділі

Приклади для оцінки складності (пиши у коментарях відповіді):

1.

void print(vector<int> arr)
{
	int sum = 0;
	int mul = 1;
	for (int i : arr)
    	sum += i;
 
	for (int i : arr)
    	mul *= i;
 
	cout << sum << " - " << mul << endl;
}

2.

void printPairs(vector<int> arr1, vector<int> arr2)
{
    for(int i1 : arr1)
    	for(int i2 : arr2)
        	for(int j = 0; j < 999999; ++j)
            	cout << i1 << ',' << i2 << endl;
}

3.

void printHalf(vector<int> arr1)
{
	for(int i = 0; i < arr1.size() / 2; ++i)
    	cout << i << endl;
}

4.

int exp(int n)
{
	if (n <= 1) return 1;
	return exp(n - 1) + exp(n - 1) + exp(n - 1);
}

5. Припустимо, що маємо різні алгоритми, які розв’язують одну і ту саму задачу:

o O(2N + 589);
o O(N + C), де відомо, що C менше N у два рази;
o O(N+M);
o O(2^N);
o O(N+logN);
o O(N³+10000000N);
o O(NlogN + N²);

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

Структури даних

«Розумні структури даних і тупий код працюють набагато краще, ніж навпаки»

Ерік Стівен Реймонд, відомий американський програміст і хакер.

Масив (Array)

Мабуть, найпопулярніша структура даних про яку вже неодноразово згадувалось у цій статті. Прийшов час розібратися.

Масив — це впорядкований скінченний набір даних (елементів) одного типу, що зберігаються в послідовно розташованих комірках оперативної пам’яті. Класичним прикладом може буде string, який є масивом послідовних символів.

Дуже важливо розуміти — у памʼяті компʼютера елементи масиву розташовуються послідовно. Це дає змогу отримати доступ до будь-якого елементу за О(1).

Приклад:

int arr[5] = {1, 2, 3, 4, 5};

Виділено достатньо пам’яті для зберігання усіх елементів масиву. В даному прикладі весь масив зайняв простір між адресами 00×451 та 00×455 (це вигадані для прикладу адреси). При чому до масиву та після можуть бути розташовані якісь дані, які не належать до цього процесу.

Коли йде звернення до масиву, то комп’ютер знає, де початок, а індекс вказує на скільки комірок стрибнути.

arr[0] = 1. Для компʼютера це означає — взяти значення, яке лежить за адресою 00×451 + 0 = 00×451, тобто 1.
arr[3] = 4 => 00×451 + 3 = 00×454 ( 4 )
arr[6] = ? У цьому випадку значення буде невизначено. Кожен раз при запуску результат буде змінюватись залежно від того, що лежить за адресою 00×451 + 6 = 00×457. Саме тому потрібно бути уважним з індексами.

З доступом по індексу зрозуміло — O(1). Що буде, якщо потрібно вставити новий чи видалити якийсь елемент з масиву? Якщо логічно подумати, то для цього потрібно фактично створити новий масив більшого розміру та перенести усі значення зі старого, вставляючи нове у потрібне місце. Цей процес займає O(N) (Виключенням буде вставка у кінець динамічного масиву (Vector у С++), там трошки інший принцип, і це тема для іншої статті).

До цього ми говорили про одновимірний масив, але є ще й двовимірний (матриця):

У пам’яті комп’ютера це буде виглядати як один великий послідовний одновимірний масив:

Наприклад:

int a[3][3] = { {1,2,3},
                {4,5,6},
                {7,8,9} };
a[0][2] = 3 => 00x451 + 2 = 00x453 ( 3 ).

У С++ існують декілька способів роботи з масивами:

int arr[5] = {1, 2, 3, 4, 5};
vector<int> arr = {1,2,3,4,5};
array<int, 5> arr = {1,2,3,4,5};

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

Зв’язний список (Linked List)

Зв’язний список — це структура даних, яка представляє послідовність вузлів. У однозв’язному списку (Linked List) кожен вузол вказує на наступний. Двозв’язний список (Doubly Linked List) вказує як на наступний, так і на попередній вузли. Перший вузол називають головою (Head) списку, а останній хвостом (Tail).

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

Linked List:

Doubly Linked List:

Це означає, що кожен новий вузол буде створений у рандомному місці пам’яті, на який буде вказувати інший. Отримати доступ до конкретного вузла вдасться, лише перевіряючи послідовно один за іншим, поки не буде знайдено бажаний. Тож, як можна зрозуміти, це буде О(N), а не О(1), як у масиві.

Але ця властивість дає іншу перевагу — вставляти новий вузол чи видаляти з кінця(якщо зберігається Tail) або початку(Head) можна за O(1), змінивши лише відповідні вказівники. Також, можливо, легко вставляти чи видаляти вузли в середині, хоча це буде O(N), але не потрібно щось копіювати.

Вставка вузла (7) на початок — О(1), вставка вузла (5) — O(N).

Приклад:

list<int> l = {1,2,3,4};
 
void printList(list<int> l)
{
	for(int i : l)
    	cout << i << endl;
}

Попередній приклад застосовує стандартний list C++, але можливо легко створити свій власний.

Приклад:

Для цього треба оголосити структуру з бажаними даними та вказівник на таку саму структуру:

struct Node {
public:
	int data;
	Node* next;
};

Потім створити саму реалізацію:

int main() {
	Node* head = new Node();
	Node* next = new Node();
	Node* tail = new Node();
	
	head->data = 1;
	head->next = next;
	
	next->data = 2;
	next->next = tail;
	
	tail->data = 3;
	tail->next = nullptr;
	
	while (head != nullptr)
	{
    	cout << head->data << endl;
    	head = head->next;
	}
	
	delete head;
	delete next;
	delete tail;
	
	return 0;
}

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

Стек (Stack)

У моєму дитинстві були спеціальні «штуки» для зберігання дисків:

Якщо покласти туди 5 дисків, то потім, щоб дістати перший покладений потрібно спершу дістати усі інші, але останній лежить з самого верху і його легко взяти.

Так само працює і структура даних стек у програмуванні. Принцип роботи називається LIFO (Last-In-First-Out), тобто останній прийшов — перший вийшов.

Не має сенсу використовувати цю структуру даних для доступу до якогось елементу всередині, бо це буде O(N). Її цінують за 0(1), коли потрібно: додати новий елемент, прочитати останній, видалити останній, перевірити, чи не порожній стек.

Класичні функції:

• push(something) — додати новий елемент;
• top() — прочитати останній елемент;
• empty() — перевірити порожній стек чи ні;
• pop() — видалити останній елемент.

Приклад:

void workWithStack ()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	
	cout << st.top() << endl;
	st.pop();
	cout << st.top() << endl;
	cout << "1(true) - empty, 0(false) - not empty => " <<st.empty() << endl;
	while(!st.empty())
	{
    	cout << st.top() << endl;
    	st.pop();
	}
}

Результат:

3
2
1(true) - empty, 0(false) - not empty => 0
2
1

Черга (Queue)

Структура даних у програмуванні копіює чергу у реальному житті. Наприклад, прийшовши в банк, ти бачиш перед собою 3 людини. Щоб зробити те, заради чого прийшов, потрібно дочекатись, коли закінчать свої справи усі попередні клієнти банку. Очевидно, що той, хто був перший у черзі, першим же й закінчить свої справи і піде додому.

Структура даних працює за принципом — FIFO (First-In-First-Out), тобто перший прийшов так само перший й вийшов. Має сенс використовувати, коли потрібно: читати перший елемент, видаляти перший елемент, додавати новий елемент у кінець, перевіряти, чи не пуста черга. Ці маніпуляції будуть мати О(1).

Так виглядає черга:

Класичні функції:

• push() — додати новий елемент у кінець черги;
• pop() — видалити елемент з початку черги;
• front() — прочитати елемент з початку черги;
• empty() — перевірити, порожня черга чи ні.

Приклад:

void workWithQueue ()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	cout << q.front() << endl;
	q.pop();
	cout << q.front() << endl;
	cout << "1(true) - empty, 0(false) - not empty => " << q.empty() << endl;
	while(!q.empty())
	{
    	cout << q.front() << endl;
    	q.pop();
	}
}

Результат:

1
2
1(true) - empty, 0(false) - not empty => 0
2
3
4
5

Дерево (Tree)

Дерево — це структура даних, яка складається з вузлів та ребер, що їх звʼязують. Кожне дерево починається з кореневого вузла (root node), який має дочірні вузли (child nodes). Своєю чергою, дочірні вузли можуть мати свої дочірні вузли й так далі.

Вузол вважається батьківським (parent node) для усіх своїх дочірніх. Таким чином кореневий вузол також є батьківським для всіх вузлів дерева. Листовий вузол (leaf node) — той, у якого немає дочірніх вузлів. Висота дерева (height) — максимальна кількість шляхів/ребер (edges) від кореневого до листового вузлів (рахуємо ребра, а не вузли). Глибина дерева — кількість ребер від вузла до кореневого вузла.

Приклад: Дерево з 10 вузлами.

• Вузол 1 — root для дерева та parent для усіх інших;
• Вузол 2 — child для 1, parent для 6 і 7;
• Вузли 6, 7, 0 та 9 — leaf nodes;
• Висота дерева — 3 (1->4->8->0);
• Глибина вузла 1 = 0, глибина вузла 6 = 2(6->2->1), глибина вузла 4 = 1(4->1).

Дерева бувають різних типів, і залежно від типу буде змінюватись алгоритм та його складність.

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

• Бінарне дерево (Binary Tree) — це дерево, у якому кожен вузол має не більше двох дочірніх. На прикладі вище — не бінарне дерево, але нижче показано бінарне:

• Бінарне дерево пошуку (Binary Search Tree або BST) — це бінарне дерево, у якому значення лівого дочірнього вузла менше або дорівнює (<=) значенню батьківського, а значення правого дочірнього вузла більше (>) (<= N(значення) <). Ця властивість повинна задовольняти кожен вузол дерева. (Залежно від умов властивість може змінитись. Наприклад, якщо відомо, що значення не будуть повторюватись, то властивість буде: < N <. У інших випадках може бути: < N <=)

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

Це бінарне дерево, але не BST. Причиною цьому є відмічений червоним кольором вузол зі значенням 4. Для вузла 10 властивість виконується: 4 <= 10 < 20. Але для вузла 5 — ні. 4 повинно бути дочірнім вузлом десь зліва від 5, щоб дерево вважалось BST.

Якщо замінити 4, скажімо, на 6, то властивість виконається для 10 та 5 і дерево буде BST:

• Збалансоване та незбалансоване (Balanced/Unbalanced) — збалансованим є дерево, у якого глибина усіх листових вузлів відрізняється не більше ніж на 1. Якщо дерево має лише один дочірній вузол, то глибина від листового не повинна бути більше за 1.

Дерево може бути BST, але не збалансованим. Тоді, наприклад, алгоритм вставки чи пошуку буде мати складність O(N), але якщо збалансувати те саме дерево — стане O(logN), бо на кожному кроці логіка буде обирати, в яку сторону піти, тим самим ділити навпіл.

• Закінчене бінарне дерево (Complete Binary Tree) — це дерево, у якому всі його рівні повністю заповнені, за винятком, можливо, останнього. На останньому рівні дерево повинно бути заповнено зліва направо.

• Повне бінарне дерево (Full Binary Tree) — це дерево, у якого кожен вузол має нуль або два дочірні вузли.

• Ідеальне бінарне дерево (Perfect Binary Tree) — це дерево, яке є закінченим і повним одночасно. Тобто усі листові вузли знаходяться на одному рівні, рівень своєю чергою заповнений максимально можливою кількістю вузлів.

При роботі з деревами дуже часто застосовують рекурсію. Взагалі існує багато алгоритмів для роботи з деревами. Звісно, усі охопити у цій статті не вдасться, але я хочу розглянути один дуже важливий та простий для розуміння — обхід бінарного дерева (Binary Tree Traversal):

1. In-Order Traversal — дійти до крайнього лівого вузла, зробити якусь дію з даними, піти у право;
2. Pre-Order Traversal — зробити якусь дію з даними, піти вліво, потім піти вправо;
3. Post-Order Traversal — дійти до крайнього лівого вузла, піти у право, зробити якусь дію з даними.

Приклад:

Створюємо бінарне дерево, заповнюємо даними та друкуємо значення всіма способами.

struct Node
{
	int data;
	Node* left;
	Node* right;
};
 
void printInorder(Node* node)
{
	if(node == nullptr) return;
	printInorder(node->left);
	cout << node->data << endl;
	printInorder(node->right);
}
 
void printPreorder(Node* node)
{
	if(node == nullptr) return;
	cout << node->data << endl;
	printPreorder(node->left);
	printPreorder(node->right);
}
 
void printPostorder(Node* node)
{
	if(node == nullptr) return;
	printPostorder(node->left);
	printPostorder(node->right);
	cout << node->data << endl;
}
 
int main()
{
	Node* root = new Node();
	root->data = 1;
 
	root->left = new Node();
	root->left->data = 2;
	root->left->left = nullptr;
	root->left->right = nullptr;
 
	root->right = new Node();
	root->right->data = 3;
	root->right->left = nullptr;
	root->right->right = nullptr;
	/*  	1
          2   3
	*/
	cout << "In-order: " << endl;
	printInorder(root);
	cout << "Pre-order: " << endl;
	printPreorder(root);
	cout << "Post-order: " << endl;
	printPostorder(root);
 
	return 0;
}

Результат:

In-order: 
2
1
3
Pre-order:
1
2
3
Post-order:
2
3
1

Хеш-таблиця (Hash Table)

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

Існує кілька способів реалізації:

1. Масив зв’язних списків та функція хешування. Функція хешування за допомогою спеціального алгоритму генерує для ключа значення int, яке застосовується як індекс масиву.

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

Наприклад:

Маємо книжку з іменами та номерами телефонів.

Як бачимо з прикладу — для Мами та Папи хеш-функція повернула один і той самий індекс, за яким зберігаються/ читаються дані у вигляді списку. Це називається колізія (Collision). Якщо список має N імен, то колізій, в теорії, може бути стільки ж.

Це говорить про поганий алгоритм функції хешування. Тобто у найгіршому випадку складність буде O(N), бо треба перевірити кожен елемент списку, але такий сценарій дуже малоймовірний і зазвичай хеш-функція реалізована добре, що дає O(1) TC як для додавання нового елементу у хеш-таблицю, так і для читання.

Без хеш-таблиці, для пошуку потрібно було б витратити гарантовано O(N).

У С++ така хеш-таблиця записується:

unordered_map<key_type,value_type> name;

Приклад:

Порахувати кількість елементів масиву та надрукувати.

void countElements(vector<int> arr)
{
    unordered_map<int, int> um;
    for(int i : arr)
    	um[i]++;
   
    for(auto pair : um)
    	cout << pair.first << " -> " << pair.second << endl;
}

Нехай маємо масив {3, 5, 5, 3, 7, 3, 1, 7}.

Результат:

1 -> 1
7 -> 2
5 -> 2
3 -> 3

2. Збалансоване дерево бінарного пошуку. Для побудови хеш-таблиці застосовується дерево.

На прикладі тієї ж книжки з контактами:

Перевагою у застосуванні саме цієї хеш-таблиці є стабільність та відсортований список по ключу. Складність завжди — O(logN).

У С++ така хеш-таблиця записується:

map<key_type,value_type> name;

Приклад:

Порахувати кількість елементів масиву та надрукувати.

void countElements(vector<int> arr)
{
    map<int, int> um;
    for(int i : arr)
    	um[i]++;
   
    for(auto pair : um)
    	cout << pair.first << " -> " << pair.second << endl;
}

Варто відзначити, що map зберігає список, відсортований за ключем (користуючись з дерева), а unordered_map — ні. Якщо потрібно зберігати лише унікальні значення, то для цього у С++ є: unordered_set<value_type> name та set<value_type> name. Складність та принцип застосування такий самий як і у map.

Памʼятай:

• unordered_map/unordered_set має О(1) TC (у найгіршому випадку O(N), що малоймовірно);
• map/set — має завжди O(logN) TC.

Граф (Graph)

Ти навіть не здогадуєшся наскільки це важлива структура даних. Використовується у багатьох алгоритмах, здатних вирішувати складні задачі. Як приклад — Google Maps, яким ми користуємося майже щоденно, застосовує одразу два алгоритми, в основі яких лежать графи — алгоритм Дейкстри (Dijkstra’s algorithm) та алгоритм А* (ці алгоритми не будуть описані у статті — пиши у коментарях, якщо хочеш про них окрему статтю).

Завдяки їм можливо знайти найкоротший шлях від точки А до точки Б. Коли ти обираєш, як долетіти, наприклад, з Києва до Маямі найкоротшим шляхом — алгоритм пошуку на сайті підрахує взагалі всі варіанти та відсортує їх від найкоротших до найдовших.

В основі лежать також графи та алгоритми роботи з ними. Прикладами я хотів лише підкреслити важливість графів у програмуванні. Їх ще можна наводити дуже багато — перейдемо до визначення.

Граф — це колекція вузлів (nodes) та ребер (edges). Вузли зв’язані з ребрами. Так, так, як і у дереві. Дерево є підвидом графу, тобто кожне дерево — це граф, але не кожен граф — дерево. Графи бувають двох типів — орієнтований/ спрямований (Directed graph) та неорієнтований/ без напрямку (Undirected graph).

«a,b,c,d,e,f» — дані для прикладу, але вони можуть бути замінені на адреси, назви міст чи аеропортів тощо. Основна відмінність між типами графів — напрямок звідки і куди можливо дістатися.

Наприклад:

Куди можливо потрапити з «a»?

Directed: b(a->b), c(a->c, a->b->c), d(a->d, a->c->d, a->b->c->d)
Undirected: все те саме, але додається — e(a->d->e, a->c->d->e, a->b->c->d->e)

Чи можливо потрапили з «c» до «a»?

Directed: ні, бо із «c» тільки в «d». Хоча із «a» до «c» можливо.
Undirected: так, із «c» до «a» та навпаки.

Куди можливо потрапити з «e»? (Напиши відповідь сам для обох типів).

Я хотів би звернути увагу на вузол «f» — також частина графу, але в обох випадках ніяк не можливо потрапити туди чи звідти.

Сусід — вузол, який знаходиться поруч та до якого можливо дістатися. Сусіди «a» — «b», «c» та «d». «d» та «f» — не мають сусідів. Сусід «e» — «d».

Граф можливо зобразити у вигляді списку сумісності(Adjacency list):

Directed:

{
a: [b,c,d],
b: [c],
c: [d],
d: [],
e: [d],
f: []
}

Undirected:

{
a: [b,c,d],
b: [a,c],
c: [a,b,d],
d: [],
e: [d],
f: []
}

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

Яким чином показати такий список у С++? Дуже просто — хеш-таблиця, у якої ключами будуть дані вузла («a,b,c,d,e,f»), а значенням — масив зв’язаних з ключем вузлів. Маю надію, ти вже вище ознайомився з масивом та хеш-таблицею, якщо ні, то спочатку ознайомся.

Для нашого прикладу виглядати це буде так:

unordered_map<string, vector<string>> graph;

Важливо вміти правильно побудувати граф та обходити його. У своєму прикладі нижче я покажу, як це зробити, але спершу зазначу, що існує два алгоритми обходу графу (Graph traversal) — у глибину (Depth first traversal) та у ширину (Breadth first traversal).

Depth first traversal — від початкового вузла перевіряється рандомний сусід (зазвичай по черзі зі списку сумісності), далі від сусіда до його сусіда і так далі. Таким чином логіка повзе у глибину. Реалізувати даний алгоритм допомагає стек (Stack) або ж застосування рекурсії. Ми розглянемо лише варіант зі стеком.

Breadth first traversal — від початкового вузла перевіряються усі сусіди по черзі, потім для кожного сусіда його сусіди і так далі. Таким чином логіка повзе у ширину. Реалізувати даний алгоритм допомагає тільки черга (Queue).

Хоча складність буде однаковою для обох(О(N+E), де N — кількість вузлів, а Е — кількість ребер), але, як бачимо на малюнках, Breadth first traversal може швидше знайти потрібний вузол коли відомо, що він ближче від стартового вузла, а Depth first traversal — коли далі.

Розберемо обидва алгоритми на прикладі друку графа (Directed).

Depth first traversal:

1. Додаємо «a» (перший зі списку) у стек та запускаємо внутрішній цикл, поки стек не стане порожній:
   
   1. Дістаємо останній зі стека і друкуємо — «a». Додаємо у стек сусідів «a» = {«b», «c», «d»};
   2. Дістаємо останній зі стека і друкуємо — «ad». Додаємо у стек сусідів «d» (їх немає) = {«b», «c»};
   3. Дістаємо останній зі стека і друкуємо — «adс». Додаємо у стек сусідів «с» («d» — вже відпрацьований і не додається) = {«b»};
   4. Дістаємо останній зі стека і друкуємо — «adсb». Додаємо у стек сусідів «b» («с» — вже відпрацьований і не додається). Стек = {}. Виходимо.
2. «b» — вже відпрацьований;
3. «c» — вже відпрацьований
4. «d» — вже відпрацьований;
5. «e» — додаємо у стек:
   
   1. Дістаємо останній зі стека і друкуємо — «adсbе». Додаємо у стек сусідів «е» ( «d» вже був відпрацьований, тож не додається ) = {} — порожній тож виходимо.
6. «f» — додаємо у стек:
   
   1. Дістаємо останній зі стека і друкуємо — «adсbеf». Додаємо у стек сусідів «f» (їх немає) = {} — порожній тож виходимо.

Результат, який надрукується: «adсbеf».

Breadth first traversal:

1. Додаємо «a» (перший зі списку) у чергу та запускаємо внутрішній цикл, поки черга не стане порожньою:
   
   1. Дістаємо перший з черги і друкуємо — «a». Додаємо у чергу сусідів «a» = {«b», «c», «d»};
   2. Дістаємо перший з черги і друкуємо — «ab». Додаємо у чергу сусідів «b» = {«c», «d», «c»};
   3. Дістаємо перший з черги і друкуємо — «abс». Додаємо у чергу сусідів «с» = {«d», «c», «d»};
   4. Дістаємо перший з черги і друкуємо — «abсd». Додаємо у чергу сусідів «d» (їх немає) = {«c», «d»};
   5. Дістаємо перший з черги і друкуємо ( «c» вже відпрацьований, тож не друкуємо ) — «abсd». Черга = {«d»};
   6. Дістаємо перший з черги і друкуємо( «d» вже відпрацьований тож не друкуємо ) — «abсd». Черга = {}. Виходимо.
2. «b» — вже відпрацьований;
3. «c» — вже відпрацьований;
4. «d» — вже відпрацьований;
5. «e» — додаємо у чергу:
   
   1. Дістаємо перший з черги і друкуємо — «abсdе». Додаємо у чергу сусідів «е» ( «d» вже був відпрацьований, тож не додаємо ) = {} — порожній тож виходимо.
6. «f» — додаємо у чергу:
   
   1. Дістаємо перший з черги і друкуємо — «abсdеf». Додаємо у чергу сусідів «f» (їх немає) = {} — порожній тож виходимо.

Результат, який надрукується: «abсdеf».

Але треба пам’ятати, що unordered_map не сортує ключі — це дає О(1) TC. Якщо застосувати map, то ключі будуть відсортовані, але TC — О(logN).

Як ти помітив — потрібно десь зберігати вузли, які вже були відпрацьовані, щоб не ходити колом. Для цього створюємо додаткову хеш-таблицю/набір(set):

unordered_set<string> visited;

Як ти вже знаєш, перевірка чи є елемент у set займає O(1).

Перейдемо до програмування: маємо масив пар — вказує які вузли зв’язані з якими.

Завдання: створити список сумісності (граф) на основі вхідного масиву та надрукувати його, застосовуючи обидва алгоритми обходу.

unordered_map<string, vector<string>> getGraph(vector<tuple<string, string>>& edges)
{
  unordered_map<string, vector<string>> graph;
  for(auto edge : edges)
	graph[get<0>(edge)].push_back(get<1>(edge));
 
  return graph;
}
 
void printDepth(unordered_map<string, vector<string>> graph)
{
	unordered_set<string> visited;
	stack<string> st;
 
	for (auto pair : graph)
	{
    	st.push(pair.first);
    	while (!st.empty())
    	{
        	string current = st.top();
        	st.pop();
        	if(visited.find(current) != visited.end()) continue;
        	visited.insert(current);
            cout << current << endl;
        	if(graph.find(current) == graph.end()) continue;
        	for(int i = 0; i < graph[current].size(); ++i)
        	{
                if(graph[current][i] != "")
                    st.push(graph[current][i]);
        	}
    	}
	}
}
 
void printBreadth(unordered_map<string, vector<string>> graph)
{
	unordered_set<string> visited;
	queue<string> q;
 
	for (auto pair : graph)
	{
    	q.push(pair.first);
    	while (!q.empty())
    	{
        	string current = q.front();
        	q.pop();
        	if(visited.find(current) != visited.end()) continue;
        	visited.insert(current);
            cout << current << endl;
        	if(graph.find(current) == graph.end()) continue;
        	for(int i = 0; i < graph[current].size(); ++i)
        	{
                if(graph[current][i] != "")
                    q.push(graph[current][i]);
        	}
    	}
	}
}
 
int main()
{
	vector<tuple<string, string>> edges
	{
    	{"a", "b"},
    	{"a", "c"},
    	{"a", "d"},
    	{"c", "d"},
    	{"e", "d"},
    	{"d", ""},
    	{"f", ""}
	};
 
	unordered_map<string, vector<string>> graph = getGraph(edges);
 
	cout << "Depth:" << endl;
	printDepth(graph);
	cout << "Breadth:" << endl;
	printBreadth(graph);
 
	return 0;
}

Результат (у тебе може відрізнятися, дивлячись як дані зберігаються у хеш-таблиці):

Depth:
d
e
f
a
c
b
Breadth:
d
e
f
a
b
c

Висновок та що далі

Сподіваюсь, що тепер ти можеш застосовувати знання у реальному житті та пояснити:

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

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

• більш розгорнута інформація стосовно структур даних, яка не увійшла у цю статтю;
• алгоритми сортування (Sorting algorithms);
• алгоритми пошуку (Searching algorithms);
• рекурсія (Recursion);
• алгоритми Дейкстри та А*;
• динамічне програмування (Dynamic programming);
• бітові маніпуляції (Bit Manipulation);
• теми, які цікавлять саме тебе.

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

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

Я буду стежити за всією активністю та читати коментарі. Також за можливості створюватиму щось «смачне» та корисне.

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

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті