Бесплатные тестовые вопросы по теме Алгоритмы и сложность с подсказками и объяснениями, трёх уровней: ключевые термины и факты, применение понятий, кейсы и анализ.
Какой класс сложности растёт быстрее всех при больших n?
Отличная работа. Хотите следующую?Готовы к следующей? 5 новых задач каждый день в каждой теме.
Алгоритм — это конечный список точных шагов, решающих задачу, например сортировку списка или поиск имени в телефонной книге.
Два алгоритма могут решать одну и ту же задачу, но тратить очень разное время. Сложность описывает, как объём работы растёт при увеличении входных данных.
Размер входных данных обозначают n: число элементов для сортировки, длина списка, число вершин графа.
Представьте поиск имени в телефонной книге на 1000 страниц. Чтение каждой страницы займёт до 1000 шагов. Если открывать книгу посередине и каждый раз делить её пополам, понадобится около 10 шагов.
Временная сложность считает шаги. Пространственная сложность считает дополнительную память. Обе записываются как функция от n.
Обычно рассматривают худший случай: наибольший объём работы среди всех входов размера n. Иногда спрашивают средний или лучший случай.
Ответ: 4 секунды. При удвоении n значение n² умножается на 2² = 4, поэтому время вырастет примерно с 1 до 4 секунд. 2 секунды были бы ответом для линейного роста, а 8 — для n³.
Запись Big O сохраняет только то, что важно при больших n. Постоянные множители отбрасывают и оставляют лишь самое быстрорастущее слагаемое.
При n = 1000 слагаемое n² равно 3 000 000, а 5n — всего 5000. Меньшие слагаемые почти не влияют на сумму.
Эти классы встречаются снова и снова, от самого медленного роста к самому быстрому:
Big O — это верхняя оценка: объём работы растёт не быстрее этого. Ω (Big Omega) — нижняя оценка, а Θ (Theta) — точная оценка, одновременно верхняя и нижняя.
Основание логарифма в Big O не важно, потому что логарифмы с разными основаниями отличаются лишь постоянным множителем.
Ответ: O(n²). При больших n доминирует слагаемое n², а постоянный множитель 2 отбрасывается. O(n) сохраняет не то слагаемое, а O(2n²) забывает отбросить константу.
Несколько алгоритмов встречаются почти в каждом курсе. Выучите их сложности как факты.
Рекурсивная функция вызывает саму себя для меньшего входа, пока не дойдёт до базового случая, на который отвечает напрямую. Время её работы записывают в виде рекуррентного соотношения:
Стоит знать три идеи построения алгоритмов. Разделяй и властвуй делит задачу, решает части и объединяет результаты. Жадный подход на каждом шаге выбирает локально лучший вариант. Динамическое программирование запоминает ответы на перекрывающиеся подзадачи, чтобы вычислять их один раз.
Ответ: O(n²). При плохих опорных элементах каждое разбиение оставляет n − 1 элементов по одну сторону, что даёт O(n²). O(n log n) — это её средний случай и худший случай сортировки слиянием.
Чтобы найти временную сложность фрагмента кода:
В теоретическом вопросе сначала назовите алгоритм или идею, о которой речь, затем вспомните его сложность и условия применения (отсортированные данные, неотрицательные веса, перекрывающиеся подзадачи).
Пройдите каждый шаг. Попробуйте предсказать следующий, прежде чем открыть его.
Какова временная сложность этого кода? for i = 1 to n: (j = 1; while j < n: j = j × 2)
n — это число, до которого работают циклы.
i изменяется от 1 до n с шагом 1, поэтому внешний цикл выполняется n раз.
j принимает значения 1, 2, 4, 8, … и останавливается, достигнув n. После k витков j = 2k, поэтому цикл остановится примерно через log₂ n витков.
Внутренний цикл находится внутри внешнего, поэтому количества перемножаются.
При n = 1024 внутренний цикл выполняется log₂ 1024 = 10 раз, поэтому тело выполняется 1024 · 10 = 10 240 раз. Это намного меньше, чем n² = 1 048 576.
O(n log n)
Ответ: O(n). Циклы, идущие один за другим, складываются: n + n = 2n, а константа отбрасывается, поэтому получается O(n). O(n²) было бы верно, только если бы один цикл находился внутри другого.
P содержит задачи, которые можно решить за полиномиальное время. NP содержит задачи, решения которых можно проверить за полиномиальное время. Каждая задача из P входит в NP; равно ли P = NP, до сих пор неизвестно.
Изучайте шаг за шагом в приложенииИзучайте шаг за шагом в приложении
Какая нотация описывает верхнюю границу роста?
O задаёт верхнюю границу, Ω — нижнюю, а Θ — точную (асимптотически точную) границу.
В отсортированном массиве вы ищете два элемента с заданной суммой, двигая по одному указателю с каждого конца внутрь. Какова временна́я сложность?
Если сумма слишком мала, левый указатель сдвигается вправо, если слишком велика — правый влево, поэтому шагов не больше n.
Алгоритм Штрассена умножает матрицы, используя 7 вместо 8 рекурсивных умножений блоков половинного размера. Каково время его работы?
При a = 7 и b = 2 член nlog₂ 7 доминирует над работой сложения O(n²), что даёт примерно n2,81.
Два алгоритма могут решать одну и ту же задачу, но тратить очень разное время. Сложность описывает, как объём работы растёт при увеличении входных данных.
Размер входных данных обозначают n: число элементов для сортировки, длина списка, число вершин графа.
У каждого вопроса четыре варианта ответа, и только один правильный. Застряли? Сначала откройте небольшую подсказку, а полное объяснение — только когда оно понадобится.