← Все вопросы
Как оценить сложность вложенного цикла, если внутренний идёт до i, а не до n?
14
Часто пишут так:
for i in range(n):
for j in range(i):
do_something()
Внутренний цикл крутится не n раз, а i раз. Это всё ещё O(n^2) или меньше? Как правильно посчитать?
3 ответа
22
✓ Принятый ответ — помог автору
Это O(n^2). Суммарное число итераций внутреннего цикла = 0+1+2+...+(n-1) = n*(n-1)/2. Это примерно n^2/2, а константу 1/2 в О-нотации выбрасывают, поэтому остаётся O(n^2). Главный признак: даже если граница переменная, но в среднем она пропорциональна n, итераций всё равно порядка n^2. Уменьшение в 2 раза асимптотику не меняет.
Ivan Ivanov Та самая формула арифметической прогрессии, которую все проходили в школе и забыли 🙂 · 2 месяца назад
9
O(n^2).
-5
O(n), внутренний же не до n идёт.
Иван Кудрявцев Нет. Сумма от 1 до n это ~n^2/2, а не n. Посчитай для n=1000 руками. · 2 месяца назад
Ваш ответ
Войдите, чтобы ответить на вопрос.
