Упражнения с вложенными циклами начнем с самого простого примера. Обратите внимание, что внутренний цикл не зависит от переменной внешнего цикла. Это значит, что можно отдельно посчитать сложность внутреннего цикла и умножить ее на количество итераций внешнего цикла.

void Sort(int[] a)
{
    for (int i = 0; i < a.Length; i++)
        for (int j = 0; j < a.Length; j++)
            if (i < j && a[i] > a[j])
            {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
}

1. Оцените сложность этого кода в зависимости от n — длины массива a 1 балл

Θ(1)

Θ(n(n-1)/2)

Θ(2n)

Θ(n)

Θ(n²)

Θ(n³)