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

Question

Куда обратиться за информацией о времени вычисления математических функций?Было ли проведено какое-либо (общее) исследование с какой-либо строгостью?

Например, время вычисления

постоянная + постоянная

обычно занимает O (1).

Предположим, я хочу начать использовать математические интегралы, и я хотел бы получить асимптотическое приближение к различным интегралам.Было ли это стандартным исследованием или я должен взять имеющуюся у меня информацию и выяснить свое собственное приближение.Я был бы очень заинтересован в стандартном подходе к этому, и я хотел бы знать, существует ли он уже.

Вот моя мотивация: я в процессе написания статьи, которая указывает на эквивалентностьмежду NP трудными задачами и определенными типами математических уравнений.Кажется, что можно использовать для изучения математических вычислений время, которое обобщается как новая наука.

РЕДАКТИРОВАТЬ: я думаю, мне интересно, есть ли стандартная вычислительная сложность для любой данной математики, которая не можетизбегать.Мне интересно, изучал ли кто-нибудь этот вопрос.Я хотел бы посмотреть, что попробовали другие.

РЕДАКТИРОВАТЬ 2: Википедия перечисляет "Теорию вычислительной сложности" в своей энциклопедии, которая, я думаю, может соответствовать всем требованиям.Мне все еще интересно, может ли кто-нибудь, кто изучал это, подтвердить это.

Answer 1

«Стандартная» математика не имеет понятия алгоритмической сложности. Это зарезервировано для компьютерных алгоритмов.

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

Вы можете спросить, какова алгоритмическая сложность интеграции Эйлера по сравнению с Рунге-Куттой пятого порядка для интеграции. Они будут сравниваться на основе количества требуемых оценок функций и стабильности шага по времени.

Но каково «время выполнения» решения последней теоремы Ферма? Как насчет последних проблем Дэвида Гильберта? Является ли «бегущее время» для тех столетий и считается? Какое у вас время для решения уравнения в частных производных с использованием разделения переменных?

Когда вы думаете об этом таким образом, вы лучше понимаете, почему люди будут откладывать на ваш вопрос?

Answer 2

Да, для различных математических функций была изучена вычислительная сложность (время выполнения) вычисления функции.Это может отличаться в зависимости от модели вычисления.

Например, добавление двух n-битных чисел занимает Θ (n) времени, умножение их занимает takes (n log n) времени (с использованием БПФ), находя их gcdзанимает Θ (n ² ) времени с обычным евклидовым алгоритмом и Θ (n (log n) ² (log log n)) с лучшими алгоритмами и т. д. Для более сложных вещей, таких какинтегралы, очевидно, это зависит от того, какой алгоритм вы используете для этого.

Answer 3

Нет собранных работ, но работа над аппроксимирующими функциями близка. Например, вы хотели бы знать, что приближение sin (x) с точностью до ошибки эпсилона может быть выполнено за время, пропорциональное некоторому полиному в log (x) и 1 / epsilon. Здесь нет общей теории (хотя вы должны искать сложность информации), и может помочь фокусировка на конкретных функциях.

Answer 4

user389117,

Я думаю, что подсознательно вы хотите вывести сложность вычисления математического типа из формы этого математического типа.

Например, математический тип, который касается квадратапеременная (x ^ 2), вы думаете (по крайней мере, подсознательно), что сложность вычисления анологична x ^ 2, поэтому сложность должна быть примерно такой, как O (n ^ 2), или существует стандартный процесс для вывода формы сложностииз формы математического уравнения.

Это оба разные качества, и одно не может вывести одно качество из другого.

Я приведу вам пример: в статьях все алгоритмы написаны напсевдокод, а затем ученые выводят сложность псевдокода.

Псевдокод должен быть неизбежно написан, а затем вы вычисляете сложность.

Не существует волшебного способа получить сложность из формы того, что вы хотите вычислить.

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

Удачи!