Tak jak w temacie, czy ktoś zna odpowiedź? W Cormenie znalazłem jedynie informację, że czas działa procedury List-Search na liście o n elementach wynosi Theta(n). Zatem złożoność wyszukiwania na liście jednokierunkowej wynosi właśnie tyle? A na dwukierunkowej?
0
2
A pomyśl chwile, ile operacji musisz wykonać żeby znaleźc w liscie losowy element. Optymistycznie będzie pierwszy. Pesymistycznie będzie ostatni, średnio będzie gdzieś w środku. No to ile elementów musisz średnio / pesymistycznie sprawdzić?
0
No według mnie w obu przypadkach będzie theta(n). W najgorszym przypadku musimy przejść przez wszystkie elementy listy, a jej dwukierunkowość nie wpłynie na złożoność pesymistyczną. Tylko nie wiem, czy dobrze myślę.
2
Dobrze myślisz. Złożoność O(n).