Систематизация сложности операций

C# и .NET Framework --- Оптимизация приложений .NET Framework --- Систематизация сложности операций

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

При обсуждении обобщенных типов и коллекций ранее, немного говорилось о сложности операций, поддерживаемых коллекциями в .NET Framework и нашими собственными реализациями коллекций. В этой статье мы подробнее расскажем, что означает «большое O» (Big-Oh) и познакомим вас с основными классами сложности, известными в информатике и теории алгоритмов.

Большое O

Обсуждая сложность операции поиска в списке List<T>, мы сказали, что он имеет сложность O(n). Если говорить простым языком, это означает, что для поиска некоторого конкретного элемента в списке с 1000 элементов в самом худшем случае (когда искомый элемент отсутствует в списке) потребуется выполнить 1000 итераций. То есть, нотация «большое O» - это оценка роста времени, необходимого на выполнение алгоритма, с увеличением объема входных данных. Однако, формальное определение может показаться немного странным:

Предположим, что функция T(A; n) выполняет несколько итераций, необходимых для вычислений по алгоритму A с входными данными, содержащими n элементов. Пусть f(n) - монотонная функция с областью определения в множестве положительных чисел. Тогда, T(A; n) - это O(f(n)), если существует такая константа "c", когда для всех n выполняется соотношение T(A; n) <= c*f(n).

Проще говоря, сложность алгоритма обозначается как O(f(n)), где f(n) является верхней оценкой фактического количества итераций алгоритма, когда объем входных данных равен n. Эта оценка не должна быть жесткой; например, можно сказать, что поиск по списку List<T> имеет сложность O(n⁴). Однако, применение такой свободной оценки не очень полезно, потому что не объясняет реальную возможность выполнить поиск по списку List<T>, даже если он содержит 1 000 000 элементов. Если бы поиск по списку List<T> имел жестко заданную сложность O(n⁴), он оказался бы крайне неэффективным даже для списков, содержащих несколько тысяч элементов.

Кроме того, верхняя оценка может быть жесткой для одних входных данных и не жесткой для других; например, если при поиске элемента в списке, который по случайному совпадению оказывается первым, количество итераций будет постоянным (равным единице!) для любого количества элементов в списке - именно поэтому в предыдущих абзацах мы говорили о худшем случае.

Ниже перечислены некоторые примеры, как эта нотация помогает оценивать время выполнения и сравнивать различные алгоритмы:

• Если один алгоритм имеет сложность 2n³ + 4, а другой - сложность Sn³ - n², мы можем сказать, что оба алгоритма имеют сложность O(n³) и они эквивалентны в смысле нотации большого O (попробуйте найти константу "c" для каждой из этих сложностей). Легко доказать, что говоря о нотации большого O, мы можем опустить любые члены, кроме наибольшего.

• Если один алгоритм имеет сложность n², а другой - сложность 100n + 5000, можно смело утверждать, что первый алгоритм медленнее второго для больших объемов входных данных, потому что в нотации большого O он имеет сложность O(n²), тогда как второй - сложность O(n). Действительно, уже для случая n = 1000 первый алгоритм оказывается намного медленнее второго.

По аналогии с верхней оценкой сложности, существует также нижняя оценка (обозначается как W(f(n))) и жесткая оценка (обозначается как Ω(f(n))). Однако эти оценки реже используются при обсуждении сложности алгоритмов, поэтому мы не будем касаться их.

Основная теорема

Основная теорема (master theorem) - это просто результат, обеспечивающий готовое решение для анализа сложности многих рекурсивных алгоритмов, разбивающих решение большой задачи на множество маленьких подзадач. Например, взгляните на следующий код, реализующий алгоритм сортировки слиянием (merge sort algorithm):

public class Program<T> where T : IComparable<T>
{
    public static List<T> MergeSort(List<T> list)
    {
        if (list.Count <= 1) 
		    return list;
			
        int middle = list.Count / 2;
		
        List<T> left = list.Take(middle).ToList();
        List<T> right = list.Skip(middle).ToList();
		
        left = MergeSort(left);
        right = MergeSort(right);
		
        return Merge(left, right);
    }

    private static List<T> Merge(List<T> left, List<T> right)
    {
        List<T> result = new List<T>();
        int i = 0, j = 0;
		
        while (i < left.Count || j < right.Count)
        {
            if (i < left.Count && j < right.Count)
            {
                if (left[i].CompareTo(right[j]) <= 0)
                    result.Add(left[i++]);
                else
                    result.Add(right[j++]);
            }
            else if (i < left.Count)
            {
                result.Add(left[i++]);
            }
            else
            {
                result.Add(right[i++]);
            }
        }
        return result;
    }
}

Чтобы определить сложность этого алгоритма, необходимо решить рекуррентное соотношение относительно времени его выполнения, T(n), которое задано рекурсивно, как T(n) = 2T(n/2) + O(n). Это объясняется тем, что каждый вызов MergeSort рекурсивно вызывает MergeSort для обеих половин оригинального списка и тратит линейное время на слияние списков (очевидно, что вспомогательный метод Merge выполняет точно n операций для списка, имеющего размер n).

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

T(n) = 
    2T(n/2) + O(n) = 
    2(2T(n/4) + O(n/2)) + O(n) = 
    2(2(2T(n/8) + O(n/4)) + O(n/2)) + O(n) = ...

Основная теорема дает конечное решение этого и многих других рекуррентных соотношений. Согласно основной теореме, T(n) = O(n*log(n)), - хорошо известное значение сложности алгоритма сортировки слиянием (фактически, оно также является оценкой сложности Ω, как и O).

Машины Тьюринга и классы сложности

Об алгоритмах и задачах часто говорят, что они принадлежат классу «P», или «NP», или «NP-полному». Так обозначаются различные классы сложности. Классификация задач по сложности помогает программистам выделять задачи, имеющие простые решения, и отвергать сложные задачи или искать упрощенные подходы к их решению.

Машина Тьюринга (MT) - это абстрактная вычислительная машина, моделирующая машину, обрабатывающую бесконечную ленту с символами на ней. Головка машины может читать или записывать символы на ленту, по одному за раз, а сама машина может находиться в одном из конечного числа состояний. Перечень операций, выполняемых машиной, полностью определяется конечным количеством правил (алгоритмом), таких как «когда в состоянии Q с ленты прочитан символ 'a', записать символ 'а'» или «когда в состоянии P с ленты прочитан символ 'а', переместить головку вправо и перейти в состояние S».

Существует также два специальных состояния: начальное состояние, в котором машина находится перед выполнением любых операций, и конечное состояние. Когда машина достигает конечного состояния, говорят, что она попала в бесконечный цикл или просто завершила выполнение. На рисунке ниже изображен пример определения машины Тьюринга - окружности - это состояния, а стрелками показаны переходы из одного состояния в другое в виде последовательностей операций "чтение --> запись --> направление перемещения головки":

Самая левая стрелка указывает на начальное состояние Q. Стрелка, образующая петлю, описывает ситуацию, когда операция чтения символа A в состоянии Q возвращает машину в состояние Q.

При обсуждении сложности алгоритмов на машине Тьюринга нет необходимости рассуждать в терминах абстрактных «итераций» - шагом вычислений является единственный переход из состояния в состояние (включая переходы в то же самое состояние).

Например, когда машине Тьюринга на рисунке подается на вход лента с исходными данными «AAAa#», она выполняет ровно четыре шага. Мы можем обобщить эту ситуацию и сказать, что когда на вход подается последовательность символов «A», за которой следуют символы «a#», машина выполняет O(n) шагов. (В действительности, для исходных данных, имеющих объем n, машина выполняет точно n + 2 шагов, то есть определение O(n) включает, например, константу c=3.)

Моделирование настоящих вычислений в терминах машины Тьюринга является достаточно сложной задачей, она предназначена служить примером при изучении теории автоматов, но не для практического использования.

Самое удивительное, что любую программу на языке C# (а в действительности и любой алгоритм, который можно выполнить на современном компьютере) можно выразить - приложив определенные усилия - в терминах операций машины Тьюринга. С некоторыми допущениями можно утверждать, что если алгоритм, реализованный на C#, имеет сложность O(f(n)), его можно переложить на язык машины Тьюринга, где он будет иметь сложность O(f²(n)). Из этого утверждения выводятся очень интересные следствия: если существует эффективный алгоритм решения задачи на машине Тьюринга, существует не менее эффективный алгоритм решения той же задачи на современном компьютере; если задача не имеет эффективного алгоритма решения на машине Тьюринга, для нее обычно не существует эффективного алгоритма решения на современном компьютере.

Мы могли бы назвать алгоритмы O(n²) эффективными, а все «более медленные» алгоритмы неэффективными, однако в теории сложности используется несколько иной подход. P - это множество всех задач, которые можно решить на машине Тьюринга за полиномиальное время. Иными словами, если A - это задача, принадлежащая множеству P (с объемом входных данных п), существует алгоритм решения ее на машине Тьюринга, который позволит получить желаемый результат на ленте за полиномиальное время (например, за O(n^k) шагов, где k - некоторое натуральное число). В теории сложности задачи, принадлежащие множеству P, считаются простыми, а алгоритмы, позволяющие получить результат за полиномиальное время - эффективными, даже если k и, соответственно, время выполнения, могут оказаться очень большими.

С позиции этого определения, все алгоритмы, рассматривавшиеся до сих пор, были эффективными. Однако некоторые из них являются «более» эффективными, другие - менее, что говорит о не очень четкой градации. Вы можете даже спросить: «Существуют ли задачи, не попадающие в множество P, задачи, не имеющие эффективного решения?». Ответ на этот вопрос: «Да». В действительности, с точки зрения теории, задач, не имеющих эффективного решения, больше, чем задач, имеющих такие решения.

Для начала рассмотрим задачу, которую нельзя решить на машине Тьюринга, независимо от эффективности алгоритма. Затем исследуем задачи, которые могут быть решены на машине Тьюринга, но не за полиномиальное время. И, наконец, обратимся к задачам, для которых неизвестно, существует ли машина Тьюринга, способная решить их за полиномиальное время, и будем предполагать, что таких машин не существует.

Задача об остановке

С математической точки зрения, задач намного больше, чем машин Тьюринга (мы говорим, что машины Тьюринга поддаются «перечислению», а задачи - нет). Это означает, что существует бесконечное множество задач, которые не могут быть решены машиной Тьюринга. Такие задачи часто называют неразрешимыми.

Задача об остановке, которую мы сейчас рассмотрим, относится к разряду неразрешимых. Задача состоит в следующем: на вход подаются программа T (или описание машины Тьюринга) и исходные данные w, на выходе возвращается true, если программа T завершит когда-либо обработку w, и false, если не завершится (войдет в бесконечный цикл).

Решение этой задачи можно даже выразить на языке C#, в виде метода, принимающего код программы в виде строки:

public static bool DoesHaltOnInput(string programCode, string input)
{
    // ...
}

... или даже в виде метода, принимающего делегата и исходные данные для него:

public static bool DoesHaltOnInput(Action<string> program, string input)
{
    // ...
}

На первый взгляд кажется, что программу можно проанализировать и определить, завершится она когда-нибудь или нет (например, исследовав в ней циклы, вызовы других и так далее), но, как оказывается, нет ни машины Тьюринга, ни программ на C#, способных решить эту задачу. Как мы пришли к такому заключению? Когда мы говорим, что существует машина Тьюринга, способная решить некоторую задачу, в доказательство достаточно просто продемонстрировать ее, но, чтобы доказать, что не существует машины Тьюринга, способной решить задачу, похоже нужно перебрать и проверить все возможные машины Тьюринга, которых бесконечное множество.

Как это распространено в математике, воспользуемся способом доказательства от противного. Допустим, что кто-то написал метод DoesHaltOnInput, выполняющий требуемую проверку. Тогда мы могли бы написать такой метод:

public static void Helper(string programCode, string input)
{
    bool doesHalt = DoesHaltOnInput(programCode, input);

    if (doesHalt)
    {
        // Вход в бесконечный цикл
        while (true) { }
    }
}

Теперь добавим вызов DoesHaltOnInput во вспомогательный метод Helper. Если DoesHaltOnInput вернет true, метод Helper войдет в бесконечный цикл; если DoesHaltOnInput вернет false, метод Helper завершится как обычно. Это противоречие доказывает, что метод DoesHaltOnInput не существует.

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

Существует множество других неразрешимых задач. Другой простой пример неразрешимой задачи - задача, связанная с определением перечислимости аргумента. Множество программ на C# поддается перечислению, потому что каждая программа представлена конечным количеством символов. Однако в интервале [0,1] существует неперечислимое множество вещественных чисел. Соответственно, должно быть вещественное число, которое не может быть выведено программой.

NP-полные задачи

Даже среди множества разрешимых задач - которые могут быть решены машиной Тьюринга - существуют задачи, не имеющие эффективного решения. Сложность выбора наилучшей стратегии в игре в шахматы на доске размером n х n растет в экспоненциальной прогрессии от n, что выводит задачу реализации игры в шахматы за пределы класса P. (Если вы любите играть в шашки, но не любите, когда компьютерные программы играют в шашки лучше людей, пусть вас утешит знание, что задача реализации игры в шашки также не попадает в класс P.)

Однако существуют задачи, считающиеся менее сложными, но для решения которых все равно не существует полиномиальных алгоритмов. Некоторые из них с успехом могли бы использоваться в реальных приложениях:

• задача коммивояжера: поиск самого выгодного маршрута, проходящего через n разных городов;

• задача о клике: поиск наибольшего подмножества вершин в графе, в котором каждые две вершины соединены ребром;

• задача о минимальном разрезе - поиск способа деления графа на два подмножества узлов, когда границу подмножеств пересекает минимальное количество ребер;

• задача пропозициональной выполнимости - определить, может ли быть удовлетворена логическая формула определенной формы (например: «A и B или C и не A») присваиванием истинных значений ее переменным;

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

Эти задачи принадлежат другому множеству задач - классу NP. Задачи из класса NP характеризуются следующим образом: если A - это задача, принадлежащая классу NP, тогда существует машина Тьюринга, которая может проверить решение задачи A для исходных данных объемом n за полиномиальное время. Например, легко можно проверить, допустимо ли присваивание истинного значения переменным и решает ли это задачу пропозициональной выполнимости, причем сложность такой проверки прямо пропорциональна количеству переменных. Аналогично, легко проверить, является ли подмножество узлов графа кликой. Иными словами, эти задачи имеют легко проверяемые решения, но не известно, являются ли эффективными эти решения.

Другая интересная особенность задач выше (и многих других), состоит в том, что если какая-либо из них имеет эффективное решение, тогда все они имеют эффективное решение. Объясняется это тем, что они могут быть выражены друг через друга. Кроме того, если любая из этих задач имеет эффективное решение, это означает, что задача принадлежит классу P, и тогда весь класс сложности NP целиком сжимается до размеров класса P, так, что выполняется равенство P = NP. На сегодняшний день, ответ на вопрос о равенстве P = NP является самой большой загадкой в теоретической информатике (большинство ученых полагают, что эти классы сложности не равны).

Задачи, проявляющие эффект свертывания класса NP в класс P, называют NP-полными задачами. Если задача оказывается NP-полной, для большинства программистов это достаточное основание, чтобы отказаться от попыток найти более эффективный алгоритм ее решения. В последующих статьях будет представлено несколько примеров NP-полных задач, имеющих вполне приемлемое приближенное или вероятностное решение.