Существует ли концепция алгоритма, вычисляющего функцию, сначала найдя другой алгоритм?

Если я правильно понимаю, алгоритм, который вычисляет значение действительной функции имеет вычислительную сложность если выполняется следующее: Когда мы вычисляем с точностью требуется порядка шагов ,$f$$O(g(n))$$f$$\delta$$g(n)$

Однако что если у нас есть алгоритм, который сначала «находит более эффективный алгоритм для вычисления », а затем вычисляет ?$f$$f$

Другими словами, что если у нас есть алгоритм который выполняет следующее:$A$

1. Найти эффективный алгоритм для вычисления .$B$$f$

2. используйте для вычисления .$B$$f$

Не в этом случае, мы больше не можем говорить о вычислительном времени, которое потребуется для вычисления , например, потому что она полностью зависит от того , алгоритм уже найден алгоритм . Другими словами, время вычислений, необходимое для вычисления если является первым составным числом, намного больше, чем время вычислений, необходимое для вычисления после того, как уже вычислено.$f(5)$$A$$B$$f(5)$$5$$f(5)$$f(3)$

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

Существует хорошо известный алгоритм, универсальный алгоритм поиска Левина, режим работы которого идентичен. Рассмотрим, например, проблему поиска удовлетворительного присваивания для формулы, которая гарантированно выполнима. Универсальный поиск Левина запускает все потенциальные алгоритмы параллельно, и, если какой-либо алгоритм выводит удовлетворительное назначение, останавливает и выводит это назначение. Если оптимальный алгоритм для задачи выполняется за время , то алгоритм Левина работает за время O ( f ( n ) ) (возможно с огромной постоянной), если он реализован правильно.$f(n)$$O(f(n))$

Хотя алгоритм Левина непрактичен (из-за огромных констант), теоретически он очень интересен. См. Статью Scholarpedia для получения дополнительной информации об универсальном поиске.

Предположим, у нас есть функция, fкоторая принимает аргумент xтипа Aи выводит другую функцию, которая принимает аргумент yтипа Bи возвращает результат типа C. По вашим словам, fпринимает аргумент xи возвращает «алгоритм», который принимает входные данные типа Bи выводит результаты типа C.

Функция fимеет тип

A → (B → C)

Действительно, он принимает x : Aи возвращает функцию типа B → C. Но такой fэквивалент эквивалентен функции, g : A × B → Cкоторая принимает оба x и yсразу и дает вам конечный результат. Действительно, между типами существует изоморфизм

A → (B → C)

и

A × B → C

потому что мы можем определить gс точки зрения fкак

g(x, y) := f(x)(y)

и мы можем определить fс точки зрения gкак

f(x) := (y ↦ g(x,y))

Операция перехода от gк fназывается каррингом, и функциональные программисты используют ее постоянно. В теории вычислимости идея взять один вход и вывести функцию (алгоритм) воплощена в теореме smn .

Ответ на ваш вопрос: «Да, люди делают это постоянно». Но есть и мораль: алгоритм, который находит алгоритм, - это всего лишь алгоритм.