Czy istnieje koncepcja algorytmu obliczającego funkcję poprzez znalezienie innego algorytmu?

Jeśli dobrze to rozumiem, algorytm, który oblicza wartość rzeczywistej funkcji ma złożoność obliczeniową O ( g ( n ) ), jeśli zachowuje następujące warunki: Gdy obliczamy f z dokładnością δ, wymaga to rzędu g ( n ) kroków.$f$$O(g(n))$$f$$\delta$$g(n)$

Co jednak jeśli mamy algorytm, który najpierw „znajdzie bardziej wydajny algorytm do obliczenia ”, a następnie oblicza f ?$f$$f$

Innymi słowy, co jeśli mamy algorytm który wykonuje następujące czynności:$A$

1. Znajdź wydajny algorytm do obliczeń f .$B$$f$

2. użyj do obliczenia f .$B$$f$

W takim przypadku nie możemy już mówić o czasie obliczeniowej zajęłoby aby obliczyć na przykład dlatego, że całkowicie zależy od tego, czy algorytm już znalazł algorytm B . Innymi słowy, czas obliczeniowy wymagany do obliczenia f ( 5 ), jeśli 5 jest pierwszą liczbą obliczoną, jest znacznie większy niż czas obliczeniowy wymagany do obliczenia f ( 5 ) po obliczeniu już f ( 3 ) .$f(5)$$A$$B$$f(5)$$5$$f(5)$$f(3)$

Moje pytanie brzmi: czy istnieje koncepcja / teoria dotycząca tego rodzaju algorytmu, który najpierw szuka innego algorytmu przed obliczeniem funkcji? W szczególności zastanawiam się nad analizą złożoności obliczeniowej takich algorytmów.

$f(n)$$O(f(n))$

Podczas gdy algorytm Levina jest niepraktyczny (ze względu na ogromne stałe), jest bardzo interesujący teoretycznie. Zobacz artykuł Scholarpedia, aby uzyskać więcej informacji na temat wyszukiwania uniwersalnego.

Załóżmy, że mamy funkcję, fktóra pobiera argument xtypu Ai generuje inną funkcję, która pobiera argument ytypu Bi zwraca wynik typu C. W twoich słowach fbierze argument xi zwraca „algorytm”, który przyjmuje dane wejściowe typu Bi generuje wyniki typu C.

Funkcja fma typ

A → (B → C)

Rzeczywiście, przyjmuje x : Ai zwraca funkcję typu B → C. Ale taka fjest równoważna funkcji g : A × B → C, które bierze zarówno x i yod razu i daje wynik końcowy. Rzeczywiście między typami występuje izomorfizm

A → (B → C)

i

A × B → C

ponieważ możemy zdefiniować gw kategoriach fjako

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

i możemy zdefiniować fw kategoriach gjako

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

Operacja przejścia od gdo fnazywa się curry, a programiści funkcjonalni używają jej przez cały czas. W teorii obliczalności idea wzięcia jednego wejścia i wyjścia funkcji (algorytmu) jest zawarta w twierdzeniu smn .

Odpowiedź na twoje pytanie brzmi: „tak, ludzie robią to cały czas”. Ale jest też morał: algorytm, który znajduje algorytm, wciąż jest tylko algorytmem.