Вложенный в то время как L oop Big O. оценить

Question

int i = 0;
int n = 20;

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

  while (i < n)
  {
    printf("this is %d", i);
    i++;
  }

  i = j;
}

Таким образом, чтобы оценить сложность времени этой функции, мой подход к оценке состоит в том, что внешний l oop выполняется n раз. Внутренний l oop работает n - 1 раз? поэтому сложность времени для этого вложенного l oop будет O(n^2)?

Answer 1

Вы можете переписать исходный код

int n = 20;
int i = 0;

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

  while (i < n) 
  {
    printf("this is %d",i);

    i++;
  }

  i = j;
}

в эквивалент :

int n = 20;

for (int i = 1; i < n; ++i) 
  for (int j = i; j < n; ++j)
    printf("this is %d", j); 

Теперь очевидно, что у вас есть O(n**2) сложность времени: у вас есть

(n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 = n * (n - 1) / 2

операций (printf(...)) и

O(n * (n - 1) / 2) = O(n**2 / 2 - n / 2) = O(n**2)

Answer 2

В последующих итерациях внутренний l oop выполняется столько раз, сколько n-1, n-2, n-3, ..., 1. Таким образом, сумма равна n (n-1) / 2, что приводит к асимптотике c сложности времени как O (n ^ 2).