Большая сложность для вложенного цикла

Question

У меня есть вопрос, здесь цикл:

for (i=0; i < n; ++i)
   for (j = 3; j < n; ++j)
           {
            ...
           }

Я вроде понимаю, как рассчитать биг-о, но я не совсем уверен, как это сделать.Внешний цикл выполняется n раз, а внутренний цикл - i раз для каждого значения i.Сложность должна быть N ^ 2 (я думаю).Ребята, можете ли вы уточнить, как это рассчитывается?Я понимаю некоторые из них, но не все.

Answer 1

Это (n*(n-3)) = n²-3n, а для очень больших n оно близко к n².Поэтому для обозначения Big-Oh я бы написал O(n²), потому что -3n можно игнорировать.

---

Просто исправление вашего теста в вопросе: внешний цикл выполняется n раз,внутренний (n-3) раз для каждой итерации во внешнем цикле.

Answer 2

Сложность не обязательно O (n ^ 2).Это на самом деле зависит от того, что происходит в «...».Если материал во внутреннем цикле имеет сложность O (1), то да, общая сложность равна O (n ^ 2).Причина в том, что на любой итерации внешнего цикла у вас есть n-3 итерации внутреннего цикла.Каждая итерация внутреннего цикла имеет 1 выполнение тела, которое мы предполагаем равным O (1).Итак, вы получите n * (n-3) казней тела.Если предположить, что тело O (1), то сложность всего этого O (n * (n-3)) = O (n ^ 2)

Answer 3

В общем случае конструкция вложенных циклов for - это O (n ^ 2), но есть некоторые исключения. В компьютерной графике нормально видеть что-то вроде:

for (int x=0; x < width; x++) {
  for (int y=0; y < height; y++) {
    // Do something on a specific pixel in the image in constant time
  }
}

И посмотрите, что он называется O (n) вместо O (n ^ 2), потому что n считается числом пикселей в некоторых контекстах, а не линейным размером изображения. Итак, «n ^ 2» уже учтено. Вероятно, существуют другие специфичные для предметной области контексты, в которых принятое определение «n» может быть не сразу очевидным, если взглянуть на код.

Answer 4

Помните, что сказал Кром: это зависит от того, что находится в многоточии.Возможно, я злоупотребляю нотацией, но я думаю, что вы могли бы сказать, что это O (mn ² ) , где m - это функция, которая ограничивает роствсе, что находится в многоточии (это может быть связано с n , но мы этого не знаем).

Вы не задавали эту часть специально, но убедитесь, что выясно, почему n ² - 3n равно O (n ² ) .Посмотрите на определение для big-O, которое говорит, что n ² - 3n ≤ cn ² , где c - постояннаянаш выбор.Когда c = 2 , мы можем переписать как n ² - 3n ≤ n ² + n ² ,что явно верно.

Answer 5

Формально вы можете использовать сигма-нотацию, чтобы получить точное число итераций и, следовательно, определить порядок роста.

Answer 6

спасибо за ответы, теперь я вижу, что внутренний цикл выполняется n-3 раза из-за того, что j начинается с 3. Внешний цикл выполняется n раз как обычно.Что касается людей, которые были сбиты с толку, что я написал проблему неправильно, это то, как проблема дана.Я трижды проверил, и это именно так, как я написал это.Большое спасибо за помощь!