Время выполнения вложенного цикла Loop, который не сбрасывается

Question

Будет ли следующий код O (n ^ 2) или O (n)?

int i=0, j=0;
while (i < n) {
  while (j < n) {
    j++;
  }
  i++;
}

Поскольку внутренний цикл while выполняется только один раз от 0 до n, я бы предположил, что он эквивалентен наличию двух отдельныхв то время как циклы, таким образом, общее время выполнения будет O (2n).

Answer 1

Это O (n) в данном конкретном фрагменте кода.Например, если n = 10 для внутреннего цикла i = 0 выполняется от j = 0 до j = 9 (10 раз), а для внутреннего цикла i = 1-9 выполняется 0 раз (так как j (10)> n (10) никогда не будетсбудется), поэтому общее время = 10 раз внешнее + 10 раз внутреннее = 20 = 2n Следовательно, сложность времени равна O (n)