Existe-t-il un concept pour un algorithme calculant une fonction en trouvant d'abord un autre algorithme?

Si je comprends bien, un algorithme qui calcule la valeur d'une fonction réelle a une complexité de calcul si les conditions suivantes sont réunies: Lorsque nous calculons à la précision requiert de l'ordre des étapes .$f$$O(g(n))$$f$$\delta$$g(n)$

Cependant, que se passe-t-il si nous avons un algorithme qui "trouve d'abord un algorithme plus efficace pour calculer ", puis calcule ?$f$$f$

En d'autres termes, que se passe-t-il si nous avons un algorithme qui fait ce qui suit:$A$

1. Trouver un algorithme efficace pour le calcul .$B$$f$

2. utilisez pour calculer .$B$$f$

Dans ce cas, nous ne pouvons plus parler du temps de calcul , il faudrait pour calculer par exemple, parce qu'il dépend entièrement de savoir si l' algorithme algorithme a déjà trouvé . En d'autres termes, le temps de calcul requis pour calculer si est le premier nombre calculé est bien supérieur au temps de calcul nécessaire pour calculer après que déjà été calculé.$f(5)$$A$$B$$f(5)$$5$$f(5)$$f(3)$

Ma question est, existe-t-il un concept / théorie sur ce type d'algorithme qui trouve d'abord un autre algorithme avant de calculer une fonction? Plus précisément, je m'interroge sur l'analyse de la complexité de calcul de ces algorithmes.

Il existe un algorithme bien connu, l'algorithme de recherche universel de Levin, dont le mode de fonctionnement est identique. Considérons par exemple le problème de trouver une affectation satisfaisante pour une formule dont la garantie est satisfiable. La recherche universelle de Levin exécute tous les algorithmes potentiels en parallèle, et si un algorithme génère une affectation satisfaisante, arrête et génère cette affectation. Si l'algorithme optimal pour le problème s'exécute au temps , alors l'algorithme de Levin s'exécute au temps (avec une constante peut-être énorme) s'il est correctement mis en œuvre.$f(n)$$O(f(n))$

Bien que l'algorithme de Levin ne soit pas pratique (en raison des énormes constantes impliquées), il est très intéressant théoriquement. Consultez l' article de Scholarpedia pour en savoir plus sur la recherche universelle.

Supposons que nous ayons une fonction fqui prend un argument xde type Aet génère une autre fonction qui prend un argument yde type Bet renvoie un résultat de type C. Dans vos mots, fprend un argument xet retourne un "algorithme" qui prend des entrées de type Bet des résultats de type C.

La fonction fa le type

A → (B → C)

En effet, il prend x : Aet retourne une fonction de type B → C. Mais un tel fest équivalent à une fonction g : A × B → Cqui prend à la fois x et yà la fois et vous donne le résultat final. En effet, il existe un isomorphisme entre les types

A → (B → C)

et

A × B → C

parce que nous pouvons définir gen termes de fcomme

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

et nous pouvons définir fen termes de gcomme

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

L'opération de passage de gà fest appelée curry et les programmeurs fonctionnels l'utilisent tout le temps. Dans la théorie de la calculabilité, l'idée de prendre une entrée et de sortir une fonction (algorithme) est incorporée dans le théorème smn .

La réponse à votre question est "oui, les gens font ça tout le temps". Mais il y a aussi une morale: un algorithme qui trouve un algorithme n'est encore qu'un algorithme.