Czy sprzęt / implementacja wpłynie na złożoność algorytmów czas / przestrzeń?

Nie jestem nawet studentem CS, więc może to być głupie pytanie, ale proszę o wyrozumiałość ...

W erze komputerów wstępnych możemy zaimplementować strukturę danych tablicowych z czymś w rodzaju tablicy szuflad. Ponieważ jeden zlokalizować szuflady z odpowiadającym indeksu przed ekstrakcji wartość z niej złożoność czas odnośnika tablicy jest , przy założeniu, że przeszukiwanie binarne.$O(log(n))$

Jednak wynalazek komputerów zrobił wielką różnicę. Współczesne komputery potrafią czytać z pamięci RAM tak szybko, że teraz uważamy, że złożoność czasowa wyszukiwania tablicy jest równa (nawet technicznie tak nie jest, ponieważ przeniesienie rejestru na większą odległość zajmuje więcej czasu itp.)$O(1)$

Innym przykładem są słowniki Python. Chociaż można uzyskać złożoność dostępu do słownika za pomocą źle napisanej, przeciążonej metody magicznej (lub śmiesznie pecha, tj. Kluczy mających wiele kolizji skrótu), zwykle przyjmuje się, że jest to O ( 1 ) . W takim przypadku złożoność czasu zależy zarówno od implementacji tablicy hashowej słowników Pythona, jak i od implementacji funkcji skrótu przez klucze.$O(n)$__hash__$O(1)$

Czy to oznacza, że ​​sprzęt / implementacja może wpływać na złożoność czasową algorytmów? (Chociaż oba przykłady dotyczą struktur danych zamiast algorytmów, te drugie są oparte na tych pierwszych i nigdy nie słyszałem o złożoności struktur danych w czasie, dlatego używam tutaj terminu „algorytmy”)

Dla mnie algorytmy są abstrakcyjne i koncepcyjne, na których właściwości, takie jak złożoność czas / przestrzeń, nie powinno mieć wpływu to, czy są one implementowane w określony sposób, ale czy tak?

Pewnie. Na pewno. Oto jak pogodzić swój dyskomfort.

Analizując czas działania algorytmów, robimy to w odniesieniu do konkretnego modelu obliczeń . Model obliczeniowy określa takie rzeczy, jak czas potrzebny na wykonanie każdej podstawowej operacji (czy czas lub tablica O ( 1 ) ?). Czas działania algorytmu może zależeć od modelu obliczeń.$O(\log n)$$O(1)$

Po wybraniu modelu obliczeniowego analiza algorytmu jest czysto abstrakcyjnym, koncepcyjnym, matematycznym ćwiczeniem, które nie zależy już od sprzętu.

Jednak w praktyce zazwyczaj chcemy wybrać model obliczeniowy, który odzwierciedla rzeczywistość naszego sprzętu - przynajmniej w rozsądnym stopniu. Jeśli więc nastąpi zmiana sprzętu, możemy zdecydować się przeanalizować nasze algorytmy w innym modelu obliczeń, który jest bardziej odpowiedni dla nowego sprzętu. W ten sposób sprzęt może wpływać na czas działania.

Nie jest to oczywiste, ponieważ w klasach wprowadzających często nie rozmawiamy o modelu obliczeniowym. Po prostu domyślnie przyjmujemy pewne założenia, nigdy nie ujawniając ich jasno. Jest to rozsądne, ze względów pedagogicznych, ale ma swoje koszty - ukrywa ten aspekt analizy. Teraz wiesz.

Myślę, że w tym pytaniu jest podstawowe nieporozumienie. Porównujesz osobę znajdującą obiekt na posortowanej liście (np. Określoną stronę w książce, biorąc pod uwagę jej numer) z komputerem, który szuka elementu z tablicy.

$O(\log n)$$O(1)$

Tak, tak, sprzęt (tj. Model obliczeń) wpływa na czas działania algorytmów, jak wyjaśnia DW , ale nie na tym opiera się twój przykład dostępu do tablicy.

Nie, sprzęt nie wpływa na złożoność algorytmów.

Wpływa jednak na wybór algorytmu i może wpływać na użyteczność analizy złożoności do tego stopnia, że ​​analiza staje się praktycznie bez znaczenia (lub ma jedynie znaczenie akademickie).

Znalezienie właściwej szuflady (jako dostępu do elementu tablicy) wykorzystuje algorytm „otwórz N-ty element bezpośrednio przez indeks”, a nie algorytm „szukaj liniowo” lub „wykonaj wyszukiwanie binarne”. Algorytmy nie są zmieniane, ale wybór.

Z drugiej strony na samą analizę złożoności, a raczej jej znaczenie, ma duży wpływ sprzęt.

Wiele algorytmów, które są gwiezdne dzięki swojej analizie złożoności, są słabo wydajne lub nawet bezużyteczne w praktyce, ponieważ nieznaczny stały czynnik wcale nie jest nieznaczny, ale dominujący .

Lub, ponieważ założenia, które kiedyś były prawdziwe (lub w większości prawdziwe), nie są już dłużej aktualne. Na przykład każda operacja jest w większości taka sama (tylko małe stałe różnice, które nie mają znaczenia), lub nie ma znaczenia, do których lokalizacji pamięci masz dostęp w jakiej kolejności. Na podstawie analizy złożoności można stwierdzić, że niektóre algorytmy są znacznie lepsze, ponieważ wymagają tylko tak wielu operacji. W praktyce może się zdarzyć, że każda operacja powoduje gwarantowane pominięcie pamięci podręcznej (lub, co gorsza, błąd strony), co powoduje, że k jest tak duże, że nie jest już nieznaczne, ale dominuje wszystko.
Jeśli algorytm A potrzebuje 500 operacji na przetworzenie zestawu danych o danym rozmiarze, a algorytm B zajmuje tylko 5, ale B powoduje 5 błędów, które spalają każdy dwadzieścia milionów cykli, to pomimo tego, co może ci powiedzieć analityka lub zdrowy rozsądek, A jest lepsze.

Doprowadziło to do zabawnych niespodzianek, takich jak np. W Hashing z kukułką kilka lat temu. Co było znacznie lepsze, ponieważ [długa lista korzyści]. Po ochłodzeniu szumu okazało się, że był znacznie gorszy, ponieważ gwarantował dwa błędy pamięci podręcznej (błędy, w przypadku większych zestawów danych) przy każdym dostępie.

Podobnie stało się z identyfikowaniem i przetwarzaniem podzbiorów danych. Często poprawnym rozwiązaniem jest w dzisiejszych czasach: „po prostu zrób to wszystko” , tzn. Zamiast zastanawiać się, co jest potrzebne do przetworzenia i zrób to, przetwarzaj cały zestaw danych liniowo, nawet jeśli potrzebujesz tylko połowy. Ponieważ wierzcie lub nie, jest to szybsze ze względu na brak nieprzewidzianych oddziałów, brak pamięci podręcznej, brak błędów strony.
Chcesz odczytać pierwsze 8 kB i ostatnie 3 kB pliku 3 MB? Cóż, przeczytaj cały plik i wyrzuć to, czego nie chcesz, ponieważ poszukiwanie będzie dziesięć razy wolniejsze niż samo czytanie całej rzeczy.

Używać mapy, ponieważ ma ona złożoność logarytmiczną? Lub tablica skrótów, która ma stały czas dostępu? Constant brzmi niesamowicie. Cóż, w przypadku elementów zawierających mniej niż tysiąc rzeczy (w zależności od sprzętu, wielkości danych i wzorca dostępu) wyszukiwanie liniowe może być równie dobre lub lepsze. Niespodzianka.

Zatem nie dotyczy to samych algorytmów , ale ich przydatności i wyboru.