0Pricing
Competitive Programming Academy · Урок

Подсчёт операций с помощью Big-O

От константной до квадратичной сложности простыми словами

«Подсчёт операций с помощью Big-O» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.

Зачем считать операции

На соревнованиях побеждает скорость. Вместо замера времени работы кода Вы оцениваете количество выполняемых им шагов. Эта оценка называется его временной сложностью. 🚀

Знакомство с Big-O

Big-O описывает, как растёт количество операций при увеличении размера входных данных n. Она не учитывает мелкие детали и сосредотачивается на главной тенденции.

Константное время O(1)

Если объём работы никогда не зависит от n, это O(1). Чтение одного элемента списка или одно сложение всегда занимают одинаковое время.

x = arr[0]
y = a + b

Линейное время O(n)

Один простой цикл по n элементам имеет сложность O(n). При удвоении входных данных объём работы примерно удваивается. Это самый распространённый рабочий вариант.

for x in arr:
    total += x

Квадратичное время O(n в квадрате)

Цикл внутри цикла по n элементам имеет сложность O(n^2). При n = 1000 это миллион шагов, и дальше их число быстро растёт.

for i in range(n):
    for j in range(n):
        check(i, j)

Логарифмическое время O(log n)

Если каждый шаг вдвое уменьшает задачу, получается O(log n). Двоичный поиск обрабатывает миллиард элементов всего примерно за 30 шагов. ✨

Лестница роста

От самого быстрого к самому медленному распространённый порядок такой: O(1), O(log n), O(n), O(n log n), O(n^2). Чем выше сложность в этом списке, тем лучше она масштабируется.

Отбрасывайте константы

Big-O игнорирует постоянные множители, поэтому O(2n) — это просто O(n). Два прохода всё равно растут линейно, поэтому множитель не меняет класс сложности.

Оставляйте только самый большой член

Когда слагаемые складываются, учитывается только растущее быстрее всех. O(n^2 + n) упрощается до O(n^2), потому что при росте n значение n^2 намного больше n.

Последовательные и вложенные циклы

Два цикла один за другим складываются: O(n + n) = O(n). Два вложенных цикла перемножаются и дают O(n^2). Именно форма циклов подсказывает ответ.

Сначала худший случай

На соревнованиях проверяют самый сложный тест, поэтому рассуждайте о худшем случае. Считайте, что цикл выполняется полностью, а не завершается досрочно.

Быстрая проверка

Пора проверить Вашу интуицию насчёт Big-O.

Повторение

Теперь Вы воспринимаете код через его рост: O(1), O(n), O(n^2) и O(log n). Отбрасывайте константы, оставляйте самый большой член и учитывайте худший случай. 🎯

Часто задаваемые вопросы

Урок «Подсчёт операций с помощью Big-O» бесплатный?

Да — полный текст урока «Подсчёт операций с помощью Big-O» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.

Чему я научусь в уроке «Подсчёт операций с помощью Big-O»?

От константной до квадратичной сложности простыми словами Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Competitive Programming Academy?

Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Подсчёт операций с помощью Big-O»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Competitive Programming Academy?

Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Подсчёт операций с помощью Big-O
  2. Практическое правило 10^8
  3. Изучите ограничения и выберите сложность
  4. Почему возникает TLE и как его заметить
← Назад к Competitive Programming Academy