Анализ временной сложности цикла в программировании

Циклы являются фундаментальной операцией в программировании и используются для решения множества задач. Многие подходы к решению проблем в кодировании включают в себя различные типы циклических структур. Фактически, некоторые подходы полностью основаны на циклах, например:

• Построение частичных решений с использованием одного цикла
• Подход с двумя указателями
• Раздвижное окно
• Обход в ширину (BFS)
• Восходящий подход в динамическом программировании
• Решение проблем с использованием структур данных, таких как стек, очередь, хеш-таблица и т. д.

Эффективность алгоритма, использующего эти подходы, часто зависит от структуры цикла и операций внутри цикла.

Есть два общих шаблона циклов, которые часто встречаются в наших решениях:

1. Одиночный цикл. Это может быть цикл, который выполняется за постоянное время, цикл, который выполняется n раз, цикл, который растет экспоненциально, цикл, который выполняется на основе определенного условия, цикл, который выполняется с структура данных, последовательные одиночные циклы и т. д.
2. Вложенные циклы. Это могут быть два вложенных цикла, три вложенных цикла, один цикл с вложенными циклами и т. д.

Один из способов разработать лучший алгоритм или оптимизировать код — научиться анализировать временную сложность циклов с использованием нотации Big-O. Этому нетрудно научиться, и, попрактиковавшись на различных шаблонах циклов, вы сможете быстро принимать решения по оптимизации, экономя время в процессе анализа.

Шаги для анализа временной сложности цикла

• Подсчет общего количества итераций цикла в наихудшем случае: мы можем получить это представление, рассмотрев наихудший сценарий, начальное и конечное значение переменной цикла, условие цикла и операцию увеличения или уменьшения. Большую часть времени цикл будет выполняться для каждого элемента данных или общего размера ввода.
• Вычисление временной сложности кода в теле цикла.Цикл выполняет этот код на каждой итерации. Этот код может содержать условные операторы, операции сравнения, операции замены, операции присваивания и т. д.
• Временная сложность цикла = (Количество итераций цикла в худшем случае) * (Временная сложность кода в теле цикла). Мы представляем это в форме записи Big-O, игнорируя члены и коэффициенты более низкого порядка.

Иногда мы также можем следовать другому простому подходу:

• Определите наиболее критическую операцию внутри цикла, которая выполняется максимальное количество раз в худшем случае. Эта критическая операция будет доминирующим фактором в функции временной сложности.
• Теперь подсчитайте общее количество этой операции для полного цикла с точки зрения размера ввода. Представление этого выражения в терминах нотации Big-O даст временную сложность цикла.

Давайте проанализируем временную сложность различных паттернов цикла.

Анализ временной сложности одного цикла for и while

Один цикл for и while, работающий с постоянным временем: O(1)

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

Здесь цикл работает постоянно и выполняет операцию O (1) на каждой итерации цикла. Временная сложность = c * O (1) = O (1) * O (1) = O (1).

Лучшие примеры таких циклов: доступ к элементу в массиве, поиск минимального значения в минимальной куче, поиск элементов в хэш-таблице [среднее O(1)], поиск медианы в отсортированном массиве, замена двух переменных и т. д.

Один цикл for выполняется n раз и увеличивается или уменьшается на константу: O(n)

Пример 1

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

Пример 2

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

Здесь оба цикла выполняются n раз и выполняют операцию O(1) на каждой итерации цикла. Временная сложность = n * O (1) = O (n) * O (1) = O (n).

Для лучшего понимания Вы можете изучить анализ этих проблем кодирования

• Лидеры в массиве
• От римского к целому
• Количество зданий, обращенных к солнцу
• Минимальный и максимальный элемент в массиве
• Задача волнового массива
• Проблема FizzBuzz
• Удалить дубликаты из отсортированного массива

Одиночный цикл for и while работает постоянно, кратно n раз: O(n)

for (int i = 1; i <= c*n; i = i + 1) 
{
    // some O(1) operation
}
int i = 1;
while (i <= c * n) 
{
    // some O(1) operation
    i = i + 1;
}

Здесь цикл выполняется cn раз и выполняет операцию O(1) на каждой итерации цикла. Временная сложность = cn * O (1) = O (n) * O (1) = O (n).

Два указателя в цикле for и while: O(n)

l = 0, r = n - 1
while (l <= r) 
{
    if (some condition) 
    {
        // some O(1) operation
        l = l + 1
    }    
    else 
    {
        // some O(1) operation
        r = r - 1
    }
    // some O(1) operation
}
for (int l = 0, r = n - 1; l <= r; ) 
{
    if (some condition) 
    {
        // some O(1) operation
        l = l + 1;
    }
    else 
    {
        // some O(1) operation
        r = r - 1;
    }
    // some O(1) operation
}

В приведенном выше цикле, исходя из некоторых условий, мы либо увеличиваем l, либо уменьшаем r на единицу и выполняем операцию O(1) на каждом шаге итерации. Цикл будет выполняться n раз, потому что l и r начинаются с противоположных концов и заканчиваются, когда l > r. Таким образом, временная сложность = n*O(1) = O(n).

Для лучшего понимания вы можете изучить анализ решения двух указателей для этих проблем с кодированием

• Найти пересечение двух массивов
• Проверить, являются ли два массива подмножествами или нет
• Найти сумму пар в массиве
• Обнаружить петлю в связанном списке
• Найди емкость с наибольшим количеством воды
• Сортировка массива 0, 1 и 2

Один цикл for и while, увеличивающий или уменьшающий на постоянный коэффициент: O(logn)

Пример 1

int i = 1;
while (i < n) 
{
    // some O(1) operation
    i = i * 2;
}
for (int i = 1; i < n; i = i*2) 
{
    // some O(1) operation
}

Пример 2

for (int i = n; i > 0; i = i/2) 
{
    // some O(1) operation
}
int i = n;
while (i > 0) 
{
    // some O(1) operation
    i = i / 2;
}

Здесь цикл работает в диапазоне от 1 до n, и переменная цикла увеличивается или уменьшается в 2 раза на каждом шаге. Поэтому нам нужно подсчитать общее количество итераций, выполненных циклом, чтобы вычислить временную сложность.

Предположим, цикл завершится через k шагов, где переменная цикла увеличивается или уменьшается в 2 раза. Тогда 2^k должно быть равно n, т.е. 2^k = n и k = logn = O(logn).

Таким образом, цикл будет запускаться O (logn) раз и выполнять операцию O (1) на каждом шаге. Временная сложность = k * O (1) = O (logn) * O (1) = O (logn).

Лучшие примеры таких шаблонов циклов: Итеративный бинарный поиск, итеративный подход к нахождению n-й степени числа, экспоненциальный поиск, итеративный подход к нахождению n-й степени матрицы и т. д.

Одиночный цикл for и while, увеличивающийся на некоторую постоянную степень: O(log(logn))

// Here c is a constant greater than 1   
for (int i = 2; i < = n; i = pow(i, c)) 
{ 
    // some O(1) operation
}
int i = 2;
while (i <= n) 
{
    // some O(1) operation
    i = pow(i, c);
}

Здесь цикл работает в диапазоне от 1 до n, но переменная контура увеличивается в i раз на константу мощности c. Итак, как же рассчитать общее количество шагов цикла? Давай подумаем!

• Первая итерация цикла начинается с i = 2.
• На второй итерации значение i = 2^c.
• На третьей итерации значение i = (2^c)^c = 2^(c²).
• И так будет до конца. На любой i-й итерации значение i = 2^(c^i).
• Цикл завершится, когда 2^(c^i) = n.

2^(c^i) = n
Let's take log of base 2 from both sides.
=> log2(2^(c^i)) = log2(n)
=> c^i = logn
Again take log of base c from both sides.
=> logc(c^i) = logc(logn)
=> i = logc(logn)
=> i = O(log(logn))

Таким образом, цикл будет запускаться logc(log(n)) количество раз, где каждая итерация занимает время O(1). Таким образом, общая временная сложность = O(log(log(n))) * O(1) = O(log(log(n))).

Последовательные одиночные циклы: O(m + n)

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

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

Для расчета таких последовательных циклов нам нужно сделать сумму временных сложностей каждого цикла. Таким образом, общая временная сложность = временная сложность цикла 1 + временная сложность цикла 2 = O (m) + O (n) = O (m + n).

Для лучшего понимания Вы можете изучить анализ этих проблем с кодированием.

• Действительный горный массив
• Равновесный индекс массива
• Произведение массива, кроме самого себя

Анализ временной сложности вложенных циклов for и while

Временная сложность вложенных циклов равна количеству выполнений самого внутреннего оператора.

Два вложенных цикла for и while: O(n²)

for (int i = 0; i < n; i = i + 1) 
{
    for (int j = 0; j < n; j = j + 1) 
    {
          // some O(1) operation
    }
}
int i = 0;
while (i < n) 
{
    int j = 0;
    while (j < n) 
    {
        // some O(1) operation
        j = j + 1;
    }
    i = i + 1;
}

В приведенном выше примере с вложенным циклом внутренний цикл выполняется n раз для каждой итерации внешнего цикла. Таким образом, общее количество итераций вложенного цикла = общее количество итераций внешнего цикла * общее количество итераций внутреннего цикла = n * n = n² = O (n²).

На каждом шаге итерации вложенный цикл выполняет операцию O(1). Таким образом, общая временная сложность = O(n²) * O(1) = O(n²).

for (int i = 0; i < n; i = i + 1) 
{
    for (int j = i + 1; j < n; j = j + 1) 
    {
        // some O(1) operation
    }
}
int i = 0;
while (i < n) 
{
    int j = i + 1;
    while (j < n) 
    {
        // some O(1) operation
        j = j + 1;
    }
    i = i + 1;
}

В приведенном выше примере с вложенным циклом внешний цикл выполняется n раз, и для каждой итерации внешнего цикла внутренний цикл выполняется (n — i) раз. Таким образом, общее количество итераций вложенного цикла = (n — 1) + (n — 2) + (n — 3)…..+ 2 + 1 = сумма арифметических рядов от i = 0 до n — 1 = n (n — 1)/2 = n²/2 — n/2 = O(n²).

На каждом шаге итерации вложенный цикл выполняет операцию O(1). Таким образом, общая временная сложность = O(n²) * O(1) = O(n²).

Примечание. Это упражнение для анализа следующего цикла.

for (int i = 0; i < n; i = i + 1) 
{
    int j = i
    while (j > 0) 
    {
        // some O(1) operation
        j = j - 1
    }
}

Для лучшего понимания Вы можете изучить анализ итеративного решения этих проблем кодирования.

• Повернуть матрицу на 90 градусов
• Печать матрицы по спирали
• Пузырьковая сортировка, сортировка выбором и сортировка вставками

Сочетание одиночных и вложенных циклов

Нам нужно сделать сумму временных сложностей каждого цикла. В таком случае временная сложность определяется временной сложностью вложенного цикла.

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

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

for (int k = 0; k < n; k = k + 1) 
{
    // some O(1) operation
}

Временная сложность = Временная сложность цикла 1 + Временная сложность цикла 2 + Временная сложность цикла 3 = O(n) + O(mn) + O(n) = O(mn).

Три вложенных цикла for и while: O(n³)

for (int i = 0; i < m; i = i + 1) 
{
    for (int j = 0; j < n; j  = j + 1) 
    {
        for (int k = 0; k < n; k  = k + 1)
        {
            // some O(1) operation
        }    
    }
}
int i = 0;
while (i < m) 
{
    int j = 0;
    while (j < n) 
    {
        int k = 0;
        while (k < n) 
        {
            // some O(1) operation
            k = k + 1;
        }
        j = j + 1;
    }
    i = i + 1;
}

Все три вложенных цикла выполняются n раз и выполняют операцию O(1) на каждой итерации, поэтому временная сложность = n * n * n*O(1) = n³ * O(1) = O(n³)*O(1) = О(n³).

for(int i = 1; i < n; i = i + 1) 
{   
    for(int j = i + 1; j < n; j = j + 1) 
    {
        for(k = i; k <= j; k = k + 1) 
        {
            // some O(1) operation
        }
    }
}
int i = 1;
while(i < n)
{
    int j = i + 1;
    while(j < n)
    {
        int k = i;
        while(k <= j)
        {
            // some O(1) operation
            k = k + 1;
        }
        j = j + 1;
    }
    i = i + 1;
}

В приведенных выше трех ситуациях с вложенными циклами внешний цикл выполняется n — 1 раз, а два внутренних цикла выполняются n — i и j — i + 1 раз. Итак, каково будет общее количество итераций вложенного цикла? Давай подумаем.

       n - 1     n        j
T(n) =   ∑       ∑        ∑    O(1)
       i = 1  j = i + 1  k = i

Теперь мы решаем это тройное суммирование, расширяя суммирование по одному.

Член более высокого порядка в T(n) равен n³, тогда T(n) = O(n³). Мы игнорируем члены и коэффициенты более низкого порядка. Примечание. В третьей строке изображения выше есть одна ошибка. Вместо + i(n — i) будет — i (n — i).

Изучите эти проблемы кодирования, чтобы узнать больше об анализе временной сложности циклов for и while.

• Найти строку с максимальным количеством 1
• N повторяющихся элементов в массиве размером 2N
• Реализовать очередь с помощью стеков
• Самый частый элемент
• Самая длинная последовательная последовательность
• Подсчитайте количество возможных треугольников
• Элемент большинства
• Тройки с нулевой суммой
• Ловушка дождевой воды
• Удалить n-й узел из конца списка
• Середина связанного списка
• Максимум последовательных
• Максимальный индекс
• Первый недостающий позитив
• Самый большой подмассив с нулевой суммой
• Самая длинная подстрока без повторяющихся символов
• Проверить, являются ли две строки анаграммой или нет
• К-й наименьший элемент
• Переместить нули
• Алгоритм сортировки подсчетом
• Проверить, равны ли два массива или нет
• Подсчитайте отдельные элементы в каждом окне
• Максимальная разница в массиве
• Максимальная сумма подмассива (алгоритм Кадане)
• Реализовать стек с помощью очередей
• Следующий больший элемент

Концептуальные блоги для дальнейшего изучения

• Анализ временной сложности рекурсии
• Проектирование и анализ алгоритма сортировки слиянием
• Проектирование и анализ алгоритма быстрой сортировки
• Основы рекурсии
• Введение в алгоритмы
• Методы решения проблем DSA
• Этапы решения проблемы DSA
• Рекурсия против итерации

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

Если у вас есть какие-либо вопросы/сомнения/отзывы, напишите нам по адресу [email protected]. Наслаждайтесь обучением, наслаждайтесь алгоритмами!