Какова сложность этого для l oop, для (int j = i; j <n; j ++)?

Question

какова сложность второго для l oop? это было бы ни? Насколько я понимаю, первый для l oop будет go n раз, но индекс во втором для l oop будет установлен вместо i.

//where n is the number elements in an array
for (int i = 0; i < n; i++) {
 for (int j = i; j < n; j++) {
   // Some Constant time task
 }
}

Answer 1

В целом, внутренняя l oop повторяется sum(1..n) раз, что составляет n * (n + 1) / 2, что составляет O (n ² )

Answer 2

Если вы попытаетесь визуализировать это как матрицу, где линии представляют i, а каждый столбец представляет j, вы увидите, что это образует треугольник со сторонами n

Пример с n будучи 4

0 1 2 3
  1 2 3
    2 3
      3

Внутренняя l oop имеет (в среднем) сложность n / 2, которая равна O (n). Общая сложность составляет n * (n + 1) / 2 или O (n ^ 2)

Answer 3

Мы можем видеть, что полная итерация l oop равна n * (n + 1) / 2. Я предполагаю, что вам понятно с приведенными выше объяснениями.

Теперь давайте найдем асимптотическую c сложность времени простым логическим способом. Большой О, начинает играть, когда значение n является большим числом, в таких случаях нам не нужно рассматривать деление на 2 (2 является константой), потому что (большое число / 2) также является большим числом.

Это оставляет нам n * (n + 1).

Как объяснено выше, поскольку n большое число, (n + 1) может быть приближено к (n). таким образом оставляя нас с (n * n).

отсюда и сложность времени O (n ^ 2).

Answer 4

Число шагов, которое нужно сделать, это Номер треугольника . Вот фрагмент кода, который я собрал в LINQpad (да, извините за ответ в C#, но, надеюсь, это все еще читабельно):

void Main()
{
    long k = 0;

    // Whatever you want
    const int n = 13;

    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            k++;
        }
    }

    k.Dump();

    triangleNumber(n).Dump();

    (((n * n) + n) / 2).Dump();
}

int triangleNumber(int number)
{
    if (number == 0) return 0;
    else return number + triangleNumber(number - 1);
}

Все 3 оператора печати (.Dump() в LINQpad) производят тот же ответ (91 для значения n, которое я выбрал, но опять же вы можете выбрать все, что захотите).

Как указали другие, это O(n^2). (Вы также можете посмотреть этот вопрос и ответ для более подробной информации).