Выбор ответа Junior Сложность спрашивают часто обновлено
Сложность двух вложенных циклов
Вопрос
Какая временная сложность у функции?
function countPairs(arr) {
let count = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === 0) count++;
}
}
return count;
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n²). Внутренний цикл идёт от i + 1, поэтому всего пар n(n-1)/2.
Варианты ответа
- O(n)
- O(n log n)
- O(n²)правильный ответ
- O(2n)
Разбор
Внутренний цикл идёт от i + 1, поэтому всего пар n(n-1)/2. Константа 1/2 отбрасывается, остаётся O(n²).
- O(n): так было бы с одним проходом.
- O(n log n): нет деления пополам или сортировки.
- O(2n): это просто O(n), и к тому же неверно по сути: проходов не два, а n.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.