⚙️ Алгоритмы · 20 вопросов · ~40 мин · ⏱ Таймер 40:00 · Средний · 👥 1 прошёл

Сложность алгоритмов и O-нотация

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

Отвечено: 0 из 20

⏱ --:--

💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 40 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.

Вопрос 1 из 20

Сколько раз увеличится c при n = 5?

1+2+\dots+n=\frac{n(n+1)}{2}

n = 5
c = 0
for i in range(1, n + 1):
    for j in range(i):
        c += 1
print(c)

12 25 15 10

Вопрос 2 из 20

Какое значение c будет напечатано?

n = 6
c = 0
for i in range(n):
    j = i
    while j < n:
        c += 1
        j += 3
print(c)

10 8 12 9

Вопрос 3 из 20

Алгоритм последовательно сравнивает искомый ключ с элементами массива и останавливается при первом совпадении. Для массива длины n сколько сравнений возможно в худшем случае?

C_{worst}(n)=n

n 1 ⌈log₂ n⌉ n²

Вопрос 4 из 20

Какая пара «число вызовов touch — число увеличений hits» будет напечатана?

touch_calls = 0

def touch(x):
    global touch_calls
    touch_calls += 1
    return x % 2 == 0

hits = 0
for i in range(8):
    if touch(i):
        hits += 1
    if i > 4 and touch(i - 1):
        hits += 1

print(touch_calls, hits)

11 4 9 6 8 6 11 6

Вопрос 5 из 20

Динамический массив увеличивает вместимость вдвое при заполнении. Почему append обычно считают амортизированно O(1), хотя отдельное расширение копирует много элементов?

Потому что число копирований при расширении не зависит от текущей длины массива Потому что амортизированная оценка учитывает только последнее расширение массива Потому что каждое расширение само по себе занимает O(1), независимо от числа копируемых элементов Потому что дорогие расширения редки, и их суммарная стоимость на длинной серии добавлений линейна

Вопрос 6 из 20

Какова временная сложность в зависимости от n?

total = 0
for i in range(n):
    for j in range(i, n):
        total += a[j]

O(n) O(n²) O(n log n) O(log n)

Вопрос 7 из 20

Какой порядок роста у этого фрагмента?

s = 0
for x in data:
    s += x

for i in range(len(data)):
    for j in range(i):
        s += data[j]

O(n²) O(n log n) O(n³) O(n)

Вопрос 8 из 20

Что на самом деле утверждает запись f(n) = O(n²)?

Для каждого n функция f(n) растёт быстрее любой функции порядка n log n Функция f(n) совпадает с n² после некоторого n без постоянного множителя Начиная с некоторого n, f(n) ограничена сверху константой, умноженной на n² Алгоритм обязательно использует не больше n² байт дополнительной памяти

Вопрос 9 из 20

Какова сложность фрагмента?

n\lfloor\log_2 n\rfloor

count = 0
for i in range(n):
    x = n
    while x > 1:
        x //= 2
        count += 1

O(n) O(n log n) O(log n) O(n²)

Вопрос 10 из 20

Рекуррентность T(n)=2T(n/2)+n описывает разбиение на две половины и линейное слияние. Каков порядок роста?

T(n)=2T(n/2)+n

O(log n) O(n) O(n²) O(n log n)

Вопрос 11 из 20

Какое изменение уменьшит дополнительную память с O(n) до O(1), сохранив разворот списка?

def reversed_copy(a):
    result = []
    for i in range(len(a) - 1, -1, -1):
        result.append(a[i])
    return result

Сначала отсортировать a, затем вернуть его Менять пары элементов a слева и справа до середины Добавлять элементы в начало result Заменить result на кортеж

Вопрос 12 из 20

Какая оценка дополнительной памяти у функции при сбалансированном делении?

def search(a, left, right, x):
    if left > right:
        return -1
    mid = (left + right) // 2
    if a[mid] == x:
        return mid
    if a[mid] < x:
        return search(a, mid + 1, right, x)
    return search(a, left, mid - 1, x)

O(n) O(log n) O(n log n) O(1)

Вопрос 13 из 20

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

И время, и память обязательно стали O(n²) Время уменьшилось с O(n²) до O(n), а дополнительная память выросла до O(n) Время осталось O(n²), память уменьшилась до O(1) Время стало O(log n), память осталась O(1)

Вопрос 14 из 20

Какова пиковая дополнительная память относительно n?

def prefixes(a):
    out = []
    current = []
    for x in a:
        current = current + [x]
        out.append(current)
    return out

O(n log n) O(1) O(n) O(n²)

Вопрос 15 из 20

Граф содержит 100 000 вершин и около 200 000 рёбер. Какое представление обычно разумнее по памяти?

Матрица расстояний между всеми парами Матрица смежности 100000×100000 Отдельная полная таблица для каждой вершины Список смежности

Вопрос 16 из 20

Сколько раз выполнится тело while при n = 1000?

n = 1000
k = 1
steps = 0
while k < n:
    k *= 10
    steps += 1
print(steps)

10 3 2 4

Вопрос 17 из 20

Каков порядок роста числа выполнений count += 1?

\Theta((\log_2 n)^2)

count = 0
i = 1
while i < n:
    j = 1
    while j < n:
        count += 1
        j *= 2
    i *= 2

O(n log n) O(log n) O(n²) O((log n)²)

Вопрос 18 из 20

Алгоритм A работает за 1000n операций, B — за n². Какое утверждение корректно?

При малых n B может быть быстрее, но при достаточно больших n выиграет A Асимптотика не позволяет сказать даже о поведении при больших n A быстрее для любого положительного n B быстрее для любого положительного n

Вопрос 19 из 20

Начиная с какого целого n второй алгоритм выполняет больше базовых операций, если считать модели буквально?

def cost_a(n):
    return 50 * n

def cost_b(n):
    return n * n

n = 49 n = 51 n = 2500 n = 50

Вопрос 20 из 20

Какой порядок функций от медленной к быстрой при n→∞?

n, log n, n log n, 2ⁿ log n, n, n log n, 2ⁿ log n, n log n, n, 2ⁿ 2ⁿ, n log n, n, log n

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу