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ą jeśli zachowuje następujące warunki: Gdy obliczamy z dokładnością wymaga to rzędu 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$

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

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

użyj do obliczenia . $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 . Innymi słowy, czas obliczeniowy wymagany do obliczenia jeśli jest pierwszą liczbą obliczoną, jest znacznie większy niż czas obliczeniowy wymagany do obliczenia po obliczeniu już . $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.

complexity-theory

— użytkownik56834
źródło

Czy powiedziałbyś, że Mathematica zasadniczo robi to, o co pytasz? Dajesz mu równania do rozwiązania, a on automatycznie określa, którego algorytmu użyć do rozwiązania tych równań, a następnie je rozwiązuje.

— user541686,

Sprawdź itu.dk/people/sestoft/pebook , jest to istotne.

— Nathan Ringo,

Odpowiedzi:

$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.

— Yuval Filmus
źródło

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)

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.

— Andrej Bauer
źródło

+1 za ostatnie zdanie. Dobrze powiedziane.

— John Coleman

f (5)

$f(5)$

c + c

$c+c$

c

$c$

f (5)

$f(5)$

f (5)

$f(5)$

c_{1} + c_{2}

$c_1+c_2$

c_{1}

$c_1$

c_{2}

$c_2$

c_{1} > c_{2}

$c_1>c_2$

@ Programmer2134 czy optymalizacje kompilatora będą koncepcją, która Cię interesuje? Nie jestem wcale pewien teorii, która się za tym kryje (szczególnie jej interakcji z teorią złożoności), ale może to być potencjalny przykład

— Mark

Hasło, którego należy szukać, to „częściowa ocena”.

— Andrej Bauer