Анализ циклов

Покажем какие сложности имеют различные виды циклов. Начнем с цикла который не зависит от входных данных, а выполняется константое время.

$$ \mathcal{O}(1)$$: цикл который выполняется константное количество раз и не зависит от размера входных данных.

// c - константа, не зависимая от n 

for (int i = 1; i <= c; i++) 
{ 
     // some O(1) expressions
}

$$\mathcal{O} (n)$$: цикл который выполняется число раз пропорциональное размеру входных данных, при этом переменная итерирования увеличивается или уменьшается на константу. К примеру следующие два цикла имет линейну сложность

   // c - положительная константа
   for (int i = 1; i <= n; i += c) 
   {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) 
   {
        // some O(1) expressions
   }

При нахождении максимума или минимума цикл будет иметь сложность $$\mathcal{O} (n)$$.

$$\mathcal{O} (n^c)$$: вложенный цикл, где $$c$$ - количество вложенных циклов. К примеру, следующие два цикла имет квадратичную $$\mathcal{O} (n^2)$$ сложность.

  for (int i = 1; i <= n; i += c) 
  {
      for (int j = 1; j <= n; j += c) 
      {
          // some O(1) expressions
      }
  }

   for (int i = n; i > 0; i += c) 
   {
      for (int j = i + 1; j <= n; j += c) 
      {
          // some O(1) expressions
      }
   }

К примеру, сортировка вставками, выбором и пузырьком имеют квадратичную сложность $$\mathcal{O} (n^2)$$.

$$\mathcal{O} (\log n)$$: цикл который выполняется число раз пропорциональное размеру входных данных, при этом переменная итерирования умножается или делится на положительну константу. К примеру следующие два цикла имеют логарифмическу сложность.

   for (int i = 0; i < n; i *= c) 
   {
       // some O(1) expressions
   }

   for (int i = n; i > 0; i /= c) 
   {
       // some O(1) expressions
   }

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

Для нахождения суммарной сложности, в случае наличия нескольких циклов, необходимо сложить сложности каждого цикла. К примеру,

   for (int i = 0; i < m; i++) 
   {  
        // some O(1) expressions
   }

   for (int i = 0; i < n; i++) 
   {
        // some O(1) expressions

Сложность такого кода равна $$\mathcal{O} (m) + \mathcal{O} (n) = \mathcal{O} (m + n)$$. При $$m = n$$, имеем $$\mathcal{O} (2n)$$, то есть $$\mathcal{O} (n)$$.