sum = 0;
for (int i = 0; i < N; i++)
for (int j = i; j ≥ 0; j--)
sum++;
Я узнал, что большой-ой, чтобы быть O (n^2), но я не уверен, как найти привязанную к нему тета. Может кто-нибудь помочь?Вычислить Big-Oh и theta на время работы
Вы можете использовать сигма-обозначения для получения асимптотических оценок для алгоритма:
Поскольку мы можем показать, что T(n)O(n^2) (верхняя асимптотическая оценка), а также в Ω(n^2) (нижняя асимптотическая оценка) , следует, что T(n) находится в Θ(n^2) («сэндвич», верхняя и нижняя асимптотика).
В случае, если неясно: обратите внимание, что внутренняя и внешняя суммы в начальных выражениях выше описывают ваши внутренние и внешние для циклов соответственно.
Это может помочь http://stackoverflow.com/questions/10376740/what-exactly-does-big-%D3%A8-notation-represent – Atri
Hi @ NewProgrammer7. Если ответ ниже решил ваш вопрос, пожалуйста, рассмотрите [принять его] (http://meta.stackexchange.com/q/5234/179419), нажав на галочку. Это указывает более широкому сообществу, что вы нашли решение и дали некоторую репутацию как самому, так и самому себе. Это не обязательно. Если вы не думаете, что ответ решает ваш вопрос, подумайте о том, чтобы дать обратную связь или обновить свой вопрос более подробно. – dfri