Складність простих алгоритмів та структур даних у JS

У попередній статті “Крок на шляху до обчислень як науки: прості алгоритми та структури даних у JS” ми обговорювали прості алгоритми (лінійні та двійкові пошуки; міхур, сортування виділення та вставки) та структури даних (об’єднані об’єкти масиву та ключа та значення. ). Тут я продовжую концепцію складності та її застосування до цих алгоритмів та структур даних.

Складність

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

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

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

Отже, існує прямий причинно-наслідковий зв’язок між кількістю виконаних операцій та кількістю елементів, які виконуються. Маючи багато сміття (елементів), потрібно вивезти його багато разів. Це може призвести до проблеми складності простору . Багато квадратних метрів (елементів) вимагає багаторазового піднесення вакуумної головки по підлозі. Це може призвести до проблеми складності часу .

Незалежно від того, чи ви вивозите сміття, чи пилососите приміщення , ви можете сказати, що кількість операцій ( O ) збільшується точно із кількістю елементів ( n ) . Якщо у мене є 1 мішок для сміття, мені доведеться вивезти сміття один раз. Якщо у мене було 2 мішки для сміття, я повинен виконувати одне і те ж завдання двічі, припускаючи, що ви фізично не можете підняти більше одного пакета одночасно. Отже, великим-O цих домашніх справ є O = n або O = функція (n) або O (n) . Це лінійна складність (пряма лінія з операцією 1: відповідність 1 елементу). Отже, виконується 30 операцій над 30 елементами (жовта лінія на графіку).

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

Пошуки

Лінійний пошук

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

Двійковий пошук

Для двійкового пошуку найкращим варіантом є O (1), тобто елемент пошуку знаходиться в середній точці. Найгірший і середній випадок є логарифм по підставі 2 л або:

Логарифм або журнал - це спосіб вираження показника ступеня для даної основи. Отже, якби було 16 елементів (n = 16), то в гіршому випадку знадобилося б 4 кроки, щоб знайти число 15 (показник = 4).

Або просто: O (log n)

Сорти

Міхур

У сортуванні за бульбашками кожен предмет порівнюється з рештою колекції, щоб визначити найбільше значення для створення бульбашок. З цієї причини в середньому до гіршого випадку його складність становить O (n²) . Подумайте про цикл, вкладений в інший цикл.

Отже, для кожного предмета ви порівнюєте його з рештою своєї колекції. Це становить 16 порівнянь (або операцій) для 4 елементів (4² = 16). Кращий випадок , якщо ваша колекція майже відсортована, для одного пункту , за винятком. Це означало б єдиний цикл порівнянь. Тобто потрібно чотири порівняння, щоб створити члена колекції з чотирьох предметів, що є складністю O (n) .

Відбір

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

Вставка

В відміну від бульбашок і вибору сортів , сортування вставка вставляє елемент в його правильне положення. Але, як і попередні сорти, для цього також потрібно порівнювати кожен предмет з рештою колекції, отже, він має середню і найгіршу складність O (n²) . Як і сортування за допомогою міхура , якщо для сортування залишився лише один елемент, для вставки елемента в правильне положення потрібен лише один раунд порівнянь. Тобто він має найкращу складність випадків O (n) .

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

Масиви

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

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

Ключ - значення парних об'єктів

Доступ , вставка або видалення значення за допомогою ключа відбувається миттєво, і тому вони мають складність O (1) . Пошук у кожному “депозитному ящику” для конкретного товару за допомогою кожного доступного ключа - це, по суті, лінійний пошук . Отже, він має складність O (n) .

Висновок

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

Довідково:

//www.udemy.com/js-algorithms-and-data-structures-masterclass/