Большой O алгоритма, который опирается на сходимость
Мне интересно, можно ли выразить временную сложность алгоритма, основанного на сходимости, с помощью записи Big O.
В большинстве алгоритмических анализов, которые я видел, мы оцениваем скорость роста нашей функции на основе размера ввода.
В случае алгоритма, который имеет некоторые критерии сходимости (где мы повторяем операцию до тех пор, пока некоторая определенная метрика ошибки не становится ниже порогового значения, или скорость, с которой метрика ошибки изменяется ниже некоторого порога), как мы можем измерить сложность времени? Количество итераций, необходимых для схода и выхода из этого цикла, кажется сложным, поскольку алгоритм сходится, как правило, зависит от содержимого ввода, а не только от его размера.
Как мы можем представить временную сложность алгоритма, основанного на сходимости, в обозначениях Big O?
3 ответа
Чтобы проанализировать алгоритм, основанный на сходимости, кажется, что мы должны доказать что-то о скорости сходимости.
Конвергенция обычно имеет условие завершения, которое проверяет, находится ли наш показатель ошибки ниже некоторого порога:
do {
// some operation with time complexity O(N)
} while (errorMetric > 0.01) // if this is false, we've reached convergence
Как правило, мы стремимся определить что-то в способе сходимости алгоритма - обычно путем определения того, что это функция чего-либо.
Например, мы можем показать, что мера ошибки алгоритма является функцией количества итераций, так что ошибка = 1 / 2^i, где i - количество итераций.
Это можно переписать с точки зрения количества итераций, например, так: iterations = log(1 / E), где E - желаемое значение ошибки.
Поэтому, если у нас есть алгоритм, который выполняет некоторую линейную операцию на каждой итерации цикла сходимости (как в примере выше), мы можем предположить, что наша временная сложность равна O(N * log(1 / E)). Скорость роста нашей функции зависит от количества ошибок, которые мы готовы допустить, в дополнение к размеру входных данных.
Таким образом, если мы можем определить какое-либо свойство относительно поведения сходимости, например, является ли оно функцией ошибки или размера входных данных, то мы можем выполнить асимптотический анализ.
Возьмем, к примеру, PageRank, в его вычислениях используется алгоритм, называемый степенной итерацией, который представляет собой алгоритм, который аппроксимирует доминирующий собственный вектор матрицы. Представляется возможным, что скорость сходимости может быть показана как функция первых двух собственных значений (показано в ссылке).
Асимптотические обозначения не полагаются на сходимость.
Согласно книге CLRS (Введение в алгоритмы, третье издание, глава 3, стр. 43):
Когда мы смотрим на входные размеры, достаточно большие, чтобы сделать релевантным только порядок роста времени выполнения, мы изучаем асимптотическую эффективность алгоритмов. То есть нас интересует, как время выполнения алгоритма увеличивается с увеличением размера ввод в пределе, так как размер ввода увеличивается без ограничений. Обычно алгоритм, который является асимптотически более эффективным, будет лучшим выбором для всех, кроме очень маленьких входных данных.
Вы упомянули, что ваш код (или идея) имеет бесконечный цикл и продолжает удовлетворять условию, и вы назвали удовлетворяющий условию сходимости, но в этом смысле сходимость не связана с асимптотическими обозначениями, такими как big Oпотому что он должен завершиться, потому что необходимым условием для того, чтобы код был алгоритмом, является завершение его итераций. Вы должны убедиться, что итерации вашего кода завершены, чтобы вы могли сказать ему алгоритм и могли асимптотически анализировать его.
Другое дело, что это правда, может быть, иногда у результата больше времени выполнения, а у другого меньше времени выполнения. Это не об асимптотическом анализе. Это лучший случай, худший случай. Мы можем показать анализ алгоритмов в лучшем или худшем случае big O или другие асимптотические обозначения. Самый надежный из них - вы анализируете свой алгоритм в худшем случае. Наконец, для анализа вашего кода вы должны точно описать шаг вашего алгоритма.
С математической точки зрения основной проблемой является оценка скорости сходимости используемого подхода. Я не очень знаком с численными методами, чтобы свободно говорить о измерениях выше 1 (матрицы и тензоры, которые вы, вероятно, больше интересуете). Но давайте возьмем другой пример решения уравнений, чем разделение пополам, уже оцененное выше как O(log(1/e)),
Рассмотрим метод Ньютона и предположим, что мы пытаемся найти один корень с точностью e=10e-8 для всех чисел с плавающей точкой. Мы имеем квадрат как Скорость сходимости, поэтому у нас есть примерно 2*log(float_range/e) цикла итераций, что означает то же самое, что и алгоритмическая сложность Bisection. O(log(range/accuracy)), если мы можем рассчитать производную за постоянное время.
Надеюсь, этот пример имеет смысл для вас.