Математическая логика и теория алгоритмов

со сложностью порядка 0(« loga п log2 log2 «). Подробнее будет изло­ жено далее. Умножение матриц. Обычный метод имеет порядок сложности 0(«^). Существует более быстрый алгоритм умножения матриц - алго­ ритм Штрассена [2], который имеет сложность порядка ). Найти кратчайший путь на графе, состоящем из п вершин и т ребер. Сложность алгоритма 0{тп) [28]. Быстрое преобразование Фурье требует 0(и logi п) арифмети­ ческих операций [2]. Задача Прима - Краскала - Кэли. Дано п городов. Нужно соединить все города телефонным кабелем так, чтобы общая длина кабеля была минимальной, Эта задача решается с помощью жадного алгоритма сложности 0( «log2n) [28]. Нахождение эйлерова цикла в графе с т ребрами. Алгоритм нахонсдения эйлерова цикла имеет сложность порядка 0(т), см., на­ пример, [22]. Задачи, для которых не существует полиномиального алго­ ритма, считаются трудно разрешимыми. Рассмотрим пример определения сложности вычислений (алго­ ритма) на примерах. Пусть задано множество S, содержащее п действительных чисел. Требуется найти наибольший и наименьший элементы из S. Положим, что каясдое одно сравнение двух любых чисел осуществляется за оди­ наковое время. Один из возможных методов состоит в поиске сначала наи­ большего элемента из S, а затем - наименьшего. Наибольший элемент можно найти, проводя «-1 сравнений, например, по следующему алго­ ритму. begin МАХ-<-произвольный элемент из S\ for все другие элементы xmS do if х>МАХ then МАХ-е-х; end. 282