Сложность 😕 база
Что такое O-нотацию простыми словами?
Способ оценить, как растёт время или память алгоритма при увеличении данных — насколько он «масштабируется».
Сложность 😕 база
Что значит O(n)?
Время растёт линейно: вдвое больше данных — вдвое больше работы.
Сложность 🤓 уверенно
Чем O(1) отличается от O(n)?
O(1) — постоянное время независимо от размера (доступ к элементу массива); O(n) — пропорционально размеру (перебор всех элементов).
Сложность 🤓 уверенно
Что хуже: O(n) или O(n²)?
O(n²) хуже — при росте данных время растёт квадратично, гораздо быстрее линейного.
Сложность 🧐 глубоко
Чем сложность в худшем случае отличается от средней?
Сложность 🧐 глубоко
Что такое амортизационный анализ?
Сложность 😎 про
Как оценить пространственную сложность алгоритма?
Сложность 😎 про
Приведи примеры алгоритмов O(n log n) и O(n²).
Сложность на практике 😕 база
Какая сложность у contains() в ArrayList и HashSet?
ArrayList — O(n), перебор. HashSet — O(1), по хэшу. Поэтому проверки «есть ли» делают через Set.
Сложность на практике 😕 база
Какая сложность у get(i) в ArrayList и LinkedList?
ArrayList — O(1), элементы в памяти подряд. LinkedList — O(n), идти по цепочке ссылок.
Сложность на практике 🤓 уверенно
Почему цикл в цикле — это O(n²) и как часто его можно убрать?
На каждый из n элементов — ещё n операций. Часто внутренний перебор заменяется на HashMap/HashSet — и получается O(n).
Сложность на практике 🤓 уверенно
Какая сложность у операций TreeMap?
O(log n) на get/put/remove — это сбалансированное дерево. Медленнее HashMap, но ключи отсортированы.
Сложность на практике 🧐 глубоко
Строка += в цикле — какая сложность и почему StringBuilder лучше?
Сложность на практике 🧐 глубоко
Что означает амортизированное O(1) у add в ArrayList?
Сложность на практике 😎 про
Почему на маленьких n асимптотика может врать (константы, кэш процессора)?
Сложность на практике 😎 про
Оцени сложность SQL-запроса: WHERE по индексу, JOIN, ORDER BY без индекса.