Dowiedziałem się dzisiaj, że analiza algorytmów różni się w zależności od modelu obliczeniowego. To jest coś, o czym nigdy nie myślałem ani nie słyszałem.
Przykładem podanym mi przez użytkownika @chi , który dalej to ilustruje :
Np. Rozważ zadanie: dany zwraca x i . W pamięci RAM można to rozwiązać w O ( 1 ), ponieważ dostęp do tablicy jest stały. Korzystając z baz TM, musimy przeskanować całe wejście, więc jest to O ( n )
To sprawia, że zastanawiam się nad językami funkcjonalnymi; Z mojego zrozumienia „Języki funkcjonalne są ściśle związane z rachunkiem lambda” (z komentarza Yuval Filmus tutaj ). Tak więc, jeśli języki funkcjonalne oparte są na rachunku lambda, ale działają na maszynach opartych na pamięci RAM, jaki jest właściwy sposób przeprowadzania analizy złożoności algorytmów implementowanych przy użyciu czysto funkcjonalnych struktur danych i języków?
Nie miałem okazji czytać czysto funkcjonalnych struktur danych, ale zajrzałem do strony Wikipedii na ten temat i wydaje się, że niektóre struktury danych zastępują tradycyjne tablice:
„Tablice można zastąpić mapą lub listą dostępu swobodnego, która dopuszcza czysto funkcjonalną implementację, ale czas dostępu i aktualizacji jest logarytmiczny”.
W takim przypadku model obliczeniowy byłby inny, prawda?
Odpowiedzi:
To zależy od semantyki języka funkcjonalnego. Nie można analizować algorytmów w językach programowania w oderwaniu, ponieważ nie wiadomo, co naprawdę oznaczają te instrukcje. Specyfikacja twojego języka musi zapewniać wystarczająco szczegółową semantykę. Jeśli twój język określa wszystko w kategoriach rachunku lambda, potrzebujesz pewnej miary kosztów dla redukcji (czy są to O (1) czy zależą od wielkości zredukowanego terminu?).
Myślę, że większość języków funkcjonalnych nie robi tego w ten sposób i zamiast tego dostarcza bardziej użytecznych instrukcji, takich jak „wywołania funkcji to O (1), a dopisywanie do nagłówka listy to O (1)”, takie rzeczy.
źródło