Большое O алгоритма, основанного на сходимости

Кажется, что для анализа алгоритма, основанного на сходимости, нам нужно что-то доказать о скорости сходимости.

Конвергенция обычно имеет условие завершения, которое проверяет, находится ли наша метрика ошибки ниже некоторого порога:

do {
  // some operation with time complexity O(N)
} while (errorMetric > 0.01) // if this is false, we've reached convergence

Как правило, мы пытаемся определить что-то о способе сходимости алгоритма - обычно определяя, что это функция чего-то.

Например, мы могли бы показать, что мера ошибки алгоритма является функцией количества итераций, так что ошибка = 1/2^i, где i — количество итераций.

Это можно переписать с точки зрения количества итераций следующим образом: итерации = log(1/E), где E — желаемое значение ошибки.

Следовательно, если у нас есть алгоритм, выполняющий некоторую линейную операцию на каждой итерации цикла сходимости (как в приведенном выше примере), мы можем предположить, что наша временная сложность равна O(N * log(1/E)). Скорость роста нашей функции зависит от количества ошибок, которые мы готовы допустить, в дополнение к размеру входных данных.

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

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

Асимптотические обозначения не полагаются на сходимость.

Согласно книге CLRS (Введение в алгоритмы, третье издание, глава 3, стр. 43):

Когда мы смотрим на объемы входных данных, достаточно большие, чтобы иметь значение только порядок роста времени выполнения, мы изучаем асимптотическую эффективность алгоритмов. с тем, как время работы алгоритма увеличивается с размером входных данных в limit, поскольку размер входных данных неограниченно увеличивается. Обычно алгоритм, который асимптотически более эффективен, будет лучшим выбором для всех входных данных, кроме очень малых.

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

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

С математической точки зрения основной проблемой является оценка скорости сходимости используемого подхода. Я не настолько знаком с численными методами, чтобы свободно говорить о измерениях выше 1 (матрицы и тензоры, которые вас, вероятно, больше интересуют). Но возьмем другой пример Решение уравнения, чем деление пополам, уже оцененное выше как O(log(1/e)).

Рассмотрим метод Ньютона и предположим, что мы пытаемся найти один корень с точностью e=10e-8. для всех чисел с плавающей запятой. У нас есть квадрат как скорость сходимости, поэтому у нас есть приблизительно 2 * log (float_range / e) итераций цикла, что означает то же самое, что и алгоритмическая сложность деления пополам O(log(range/accuracy)), если мы можем вычислить производную за постоянное время.

Надеюсь, этот пример имеет смысл для вас.