Як змінюється тимчасова складність операції додавання елемента в кінець динамічного масиву з амортизованим резервуванням?

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

Тип даних у програмуванні

Послідовність інструкцій або дій для розв'язання задачі

Пристрій комп'ютерного обладнання

Точну кількість операцій, які виконає алгоритм

Час виконання в секундах

Точний обсяг пам'яті в байтах

Як масштабується витрата часу або пам'яті при збільшенні розміру вхідних даних

Що характеризує нотація «Big O» (O-нотація)?

Яка тимчасова складність доступу до елемента масиву за індексом у типовій реалізації масиву в пам'яті?

Масив повинен містити лише унікальні елементи

Масив повинен бути відсортованим

Масив має бути реалізований через зв'язаний список

Масив має бути статичним за розміром

Яка вимога є обов'язковою для застосування бінарного пошуку?

Статичний масив автоматично розширюється при додаванні елементів

Динамічний масив завжди має фіксований розмір

Статичному масиву неможливо звернутися по індексу

У статичному масиві розмір зафіксований, а динамічний може виділяти нові блоки і копіювати дані при розширенні

Чим відрізняються статичний і динамічний масиви з точки зору управління пам'яттю?

Масив із властивостями-ключами замість індексів

Масив, що містить пропуски (empty slots) і різнорідні типи

Масив, де всі елементи розташовані під суцільними індексами і мають однаковий тип

Об'єкт із парами ключ-значення

У JavaScript що з переліченого зазвичай вважається "щільним" (dense) масивом?

Копіюється посилання на область у купі

Копіюється саме значення (по значенню)

Одна змінна перетворюється у вказівник

Значення зберігається тільки у глобальній пам'яті

Як відбувається присвоєння примітивного значення між змінними (наприклад, number) у більшості мов?

Цикл, який виконується за допомогою for/while

Метод оптимізації виконання коду компілятором

Функція, що викликає сама себе та має базовий випадок для виходу

Тип даних для зберігання чисел

Що таке рекурсія в програмуванні?

Яка тимчасова складність алгоритму бінарного пошуку на відсортованому масиві з n елементів?

Яка складність за часом у середньому у QuickSort (швидка сортування) для n елементів?

Обчислення хеш-функції для кожного елемента

Поділ масиву на підмасиви, сортування їх і об'єднання результатів

Перебір усіх можливих перестановок

Заміна елементів тільки зі сусідніми

Який принцип лежить в основі сортування методом "розділяй і володарюй"?

Послідовність елементів, що зберігаються суцільно в пам'яті

Колекція ключ-значення на основі хеш-таблиці

Набір вузлів, кожен з яких містить значення і посилання на сусідні вузли

Спеціальний вид масиву для тільки чисел

Що називають зв'язним (linked) списком?

O(n) — потрібно пройти від початку до потрібного місця

Яка тимчасова складність доступу до довільного елемента у зв'язаному списку?

Елементи вибираються довільно

Елементи завжди видаляються з кінця

Який принцип роботи черги (queue)?

Random Access (доступ у довільному порядку)

Який принцип роботи стека (stack)?

Кожен вузол містить два значення

Кожен вузол містить посилання і на попередній, і на наступний вузол

Зберігає дані у двох різних масивах

Не підтримує видалення елементів

Що таке двонаправлений (doubly) зв'язаний список у порівнянні з однобічним?

Одновимірний масив чисел

Набір вузлів (вершин) та ребер (зв'язків) між ними

Таблиця з двома стовпцями

Тип сортування для списків

Що таке граф у структурі даних?

Список суміжності підходить для щільних графів, а матриця — для розріджених

Матриця зручніша для зберігання назв вершин у вигляді рядків

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

Вони ідентичні за пам'яттю та швидкістю для будь-якого графа

Яка різниця між списком суміжності (adjacency list) та матрицею суміжності (adjacency matrix) для представлення графу?

Який алгоритм зазвичай використовують для пошуку найкоротшого шляху у взваженому графі з невід'ємними вагами ребер?

BFS використовує стек, а DFS — чергу

BFS використовує чергу, а DFS — стек або рекурсію

Обидва використовують лише масив

BFS і DFS не використовують ніяких додаткових структур даних

Чим відрізняється обхід в ширину (BFS) від обходу в глибину (DFS) у графі з точки зору структури даних, яка використовується?

Повільно зростає і підходить для великих n

Зростає дуже швидко, набагато швидше за поліноміальні функції

Що таке факторіальна складність (O(n!)) і як вона поводиться при зростанні n?

Питання 5 з 22