⚙️ Алгоритмы · 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)

25 15 10 12

Вопрос 2 из 20

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

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

12 8 10 9

Вопрос 3 из 20

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

C_{worst}(n)=n

⌈log₂ n⌉ n n² 1

Вопрос 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)

8 6 11 4 11 6 9 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 log n) O(log n) O(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 log n) O(n²) O(n) O(n³)

Вопрос 8 из 20

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

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

Вопрос 10 из 20

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

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

O(log n) O(n log n) O(n) O(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

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

Вопрос 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(1) O(n log n) O(log n) O(n)

Вопрос 13 из 20

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

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

Вопрос 14 из 20

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

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

O(1) O(n) O(n²) O(n log 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)

2 10 3 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((log n)²) O(n²) O(n log n) O(log n)

Вопрос 18 из 20

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

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

Вопрос 19 из 20

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

def cost_a(n):
    return 50 * n

def cost_b(n):
    return n * n

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

Вопрос 20 из 20

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

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

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

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

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

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