Jak modeluje się złożoność algorytmu dla języków funkcjonalnych?

Złożoność algorytmu została zaprojektowana w taki sposób, aby była niezależna od szczegółów niższego poziomu, ale opiera się na modelu imperatywnym, np. Dostęp do tablicy i modyfikowanie węzła w drzewie zajmuje O (1). Nie dotyczy to wyłącznie języków funkcjonalnych. Dostęp do listy Haskell zajmuje liniowy czas. Modyfikowanie węzła w drzewie wymaga wykonania nowej kopii drzewa.

Czy zatem powinno istnieć alternatywne modelowanie złożoności algorytmu dla języków funkcjonalnych?

Jeśli założymy, że rachunek jest dobrym modelem funkcjonalnych języków programowania, można pomyśleć: λ- rachunek ma pozornie proste pojęcie złożoności czasowej: wystarczy policzyć liczbę kroków redukcji β ( λ x . M ) N → M [ N / x ] .$\lambda$$\lambda$$\beta$$(\lambda x.M)N \rightarrow M[N/x]$

Ale czy to dobra miara złożoności?

Aby odpowiedzieć na to pytanie, powinniśmy przede wszystkim wyjaśnić, co rozumiemy przez miarę złożoności. Dobrą odpowiedź daje teza Slot i van Emde Boasa : każda dobra miara złożoności powinna mieć wielomianowy związek z kanonicznym pojęciem złożoności czasowej zdefiniowanej za pomocą maszyn Turinga. Innymi słowy, powinno istnieć „rozsądne” kodowanie Od terminów λ- rachunek do maszyn Turinga, takich jak dla niektórych wielomianów p , jest tak, że dla każdego terminu M o rozmiarze | M | : M zmniejsza się do wartości w p ( | M $tr(.)$$\lambda$$p$$M$$|M|$$M$β - krokiredukcjidokładnie wtedy, gdy t r ( M ) zmniejsza się do wartości w p ( | t r ( M ) | ) kroków maszyny Turinga.$p(|M|)$ $\beta$$tr(M)$$p(|tr(M)|)$

Przez długi czas nie było jasne, czy można to osiągnąć za pomocą rachunku λ. Główne problemy są następujące.

• Istnieją terminy, które tworzą normalne formy (wielomianowe kroki), które mają wielkość wykładniczą. Nawet zapisywanie normalnych formularzy zajmuje dużo czasu.
• Wybrana strategia redukcji odgrywa ważną rolę. Na przykład istnieje rodzina terminów, która zmniejsza wielomianową liczbę równoległych kroków β (w sensie optymalnej redukcji λ ), ale których złożoność nie jest elementarna (co oznacza gorsze niż wykładnicze).

$\beta$

Nie jestem pewien, jaka jest sytuacja w przypadku innych strategii oceny. Nie wiem, czy podobny program został przeprowadzony dla złożoności przestrzeni.

Złożoność algorytmu została zaprojektowana w taki sposób, aby była niezależna od szczegółów niższego poziomu.

Nie, nie bardzo. Zawsze liczymy operacje elementarne w niektórych modelach maszyn:

• Kroki dla maszyn Turinga.
• Podstawowe operacje na pamięciach RAM.

$\Omega$$\Theta$$O$$\Theta$

Dlatego twoje pytanie ma prostą odpowiedź: napraw model maszyny i które „operacje” policzyć. To daje do środka. Jeśli chcesz, aby wyniki były porównywalne z niefunkcjonalnymi algorytmami, najlepiej byłoby skompilować swoje programy do pamięci RAM (do analizy algorytmów) lub TM (do teorii złożoności) i przeanalizować wynik. Twierdzenia o przeniesieniu mogą istnieć, aby ułatwić ten proces.

Zamiast formułować miarę złożoności w odniesieniu do jakiejś podstawowej maszyny abstrakcyjnej, możesz upiec koszt w samych definicjach języka - nazywa się to Dynamiką Kosztów . Do każdej reguły oceny w języku przypisuje się koszty w sposób kompozycyjny - to znaczy, że koszt operacji jest funkcją kosztu jej podwyrażeń. Takie podejście jest najbardziej naturalne w przypadku języków funkcjonalnych, ale można je zastosować w każdym dobrze zdefiniowanym języku programowania (oczywiście większość języków programowania niestety nie jest dobrze zdefiniowana).