[Algorytmy] Tablica, rekurencja, słownik

[anka0501]

Witajcie !
Mam tu 2 zad z którymi nie mogę sobie poradzić:
1. Zaproponuj algorytm rekurencyjny, realizujący sekwencyjne przegladanie, w celu znalezienia pozycji el x w dowolnym skończonym ciągu zapisanym w tablicy. Zrealizuj tę samą ideę przy założeniu, że dane elementy tworza listę dynamiczną, której ogniwo ma 2 atrybuty: wartość elementu i referencję do następnego elementu.

2. Dany jest plik, który chcemy sprawdzić oraz (plik) słownik. Należy wypisać wszystkie słowa znajdujące się w sprawdzanym pliku, których nie ma w pliku słownika.
a) jakich struktur użyłbyś do napisania programu (chodzi o najlepszą złożoność) uzasadnij wybór.
b) podaj pseudokod
c) jaka jest złożoność obliczeniowa programu względem ilości słów sprawdzanym pliku (n) i w pliku słownika (m) ?
Z góry dziękuje za pomoc.

[Kamulec]

Jeżeli nie wie się nic na temat zbioru danych, trzeba sprawdzać po kolei, czyli
1. Jeżeli lista jest pusta, to zwróć -1 i zakończ, inaczej przejdź do 2.
2. Weź następny element
3. Jeżeli element = poszukiwany, to zwróć pozycję i zakończ, inaczej odrzuć element i wróć do punktu 1.

Przy liście też trzeba porównać każdy kolejny brany element sprawdzanego pliku i porównywać z każdym elementem pliku słownika, czyli złożoność n*m (rośnie wprost proporcjonalnie do m i do n).

Oba algorytmy mogłyby nabrać nieco finezji, gdyby były dodatkowe założenia np. co do sortowania danych, czy wielkości plików.

[anka0501]

ok dzięki, tylko już trochę po czasie, bo już po egzaminie