← Все вопросы
Что такое сложность O(n) простыми словами?
6
Везде пишут O(n), O(n²), O(log n). Понимаю, что это про скорость, но как это читать и зачем мне как новичку?
2 ответа
11
✓ Принятый ответ — помог автору
O(...) — это как растёт время работы при росте данных, без привязки к конкретному железу.
- O(1) — постоянно (доступ по индексу).
- O(n) — линейно (один проход по списку): 2× данных → 2× времени.
- O(n²) — квадратично (вложенные циклы): 2× данных → 4× времени. На больших n — больно.
- O(log n) — очень медленно растёт (бинарный поиск): 1000× данных → всего ~10× времени.
Зачем новичку: чтобы понимать, почему решение «висит» на больших данных и как из O(n²) сделать O(n).
Михаил Виноградов пример с «2× данных → 4× времени» наглядно, спасибо · вчера
2
кратко: O — про масштабируемость, а не про «быстро/медленно» на одном тесте
Ваш ответ
Войдите, чтобы ответить на вопрос.
