Podstawy teorii złożoności obliczeniowej EITC/IS/CCTF

Ponieważ ilość zasobów wymaganych do uruchomienia algorytmu różni się w zależności od wielkości danych wejściowych, złożoność jest zwykle wyrażana jako funkcja f(n), gdzie n jest wielkością danych wejściowych, a f(n) jest złożonością najgorszego przypadku ( maksymalna ilość zasobów wymaganych dla wszystkich nakładów wielkości n) lub złożoność średniego przypadku (średnia ilość zasobów dla wszystkich nakładów wielkości n). Liczba wymaganych operacji elementarnych na wejściu o rozmiarze n jest powszechnie określana jako złożoność czasowa, gdzie uważa się, że operacje elementarne zajmują stałą ilość czasu na określonym komputerze i zmieniają się tylko o stały współczynnik, gdy są wykonywane na innej maszynie. Ilość pamięci wymaganej przez algorytm na wejściu o rozmiarze n jest znana jako złożoność przestrzeni.

Czas jest najczęściej branym pod uwagę zasobem. Kiedy termin „złożoność” jest używany bez kwalifikatora, zwykle odnosi się do złożoności czasu.

Tradycyjne jednostki czasu (sekundy, minuty itd.) nie są wykorzystywane w teorii złożoności, ponieważ są zbyt zależne od wybranego komputera i zaawansowania technologii. Na przykład, dzisiejszy komputer może wykonać algorytm znacznie szybciej niż komputer z lat sześćdziesiątych, jednak jest to spowodowane przełomem technologicznym w sprzęcie komputerowym, a nie nieodłączną jakością algorytmu. Celem teorii złożoności jest ilościowe określenie nieodłącznych potrzeb czasowych algorytmów lub podstawowych ograniczeń czasowych, które algorytm nałożyłby na dowolny komputer. Osiąga się to poprzez zliczenie, ile podstawowych operacji jest wykonywanych podczas obliczeń. Procedury te są powszechnie określane jako kroki, ponieważ uważa się, że zajmują one stały czas na określonej maszynie (tj. nie ma na nie wpływu ilość danych wejściowych).

Kolejnym ważnym zasobem jest ilość pamięci komputera wymagana do wykonywania algorytmów.

Innym często używanym zasobem jest ilość operacji arytmetycznych. W tym scenariuszu używany jest termin „złożoność arytmetyczna”. Złożoność czasowa jest generalnie iloczynem złożoności arytmetycznej przez stały czynnik, jeśli znane jest górne ograniczenie rozmiaru binarnej reprezentacji liczb, które występują podczas obliczeń.

Wielkość liczb całkowitych wykorzystywanych podczas obliczeń nie jest ograniczona dla wielu metod i nierealistyczne jest założenie, że operacje arytmetyczne wymagają ustalonej ilości czasu. W rezultacie złożoność czasowa, znana również jako złożoność bitowa, może być znacznie wyższa niż złożoność arytmetyczna. Arytmetyczna trudność obliczenia wyznacznika nn macierzy liczb całkowitych, na przykład, wynosi O(n^3) dla standardowych technik (eliminacja Gaussa). Ponieważ wielkość współczynników może rozszerzać się wykładniczo podczas obliczeń, złożoność bitowa tych samych metod jest wykładnicza w n. Jeśli te techniki są używane w połączeniu z arytmetykami wielomodułowymi, złożoność bitową można zmniejszyć do O(n^4).

Formalnie złożoność bitowa odnosi się do liczby operacji na bitach wymaganych do uruchomienia algorytmu. Równa się złożoności czasowej do stałego współczynnika w większości paradygmatów obliczeniowych. Liczba operacji na słowach maszynowych wymaganych przez komputery jest proporcjonalna do złożoności bitowej. W przypadku realistycznych modeli obliczeń złożoność czasowa i złożoność bitowa są zatem identyczne.

Zasobem często branym pod uwagę przy sortowaniu i wyszukiwaniu jest ilość porównań wpisów. Jeśli dane są dobrze uporządkowane, jest to dobry wskaźnik złożoności czasowej.

Na wszystkich potencjalnych wejściach zliczanie liczby kroków w algorytmie jest niemożliwe. Ponieważ złożoność danych wejściowych rośnie wraz z ich rozmiarami, jest ona powszechnie reprezentowana jako funkcja rozmiaru danych wejściowych n (w bitach), a więc złożoność jest funkcją n. Jednak w przypadku danych wejściowych o tej samej wielkości złożoność algorytmu może się znacznie różnić. W rezultacie rutynowo stosuje się różne funkcje złożoności.

Złożoność najgorszego przypadku jest sumą całej złożoności dla wszystkich wielkości n danych wejściowych, podczas gdy średnia złożoność jest sumą całej złożoności dla wszystkich wielkości n danych wejściowych (ma to sens, ponieważ liczba możliwych danych wejściowych o danym rozmiarze wynosi skończone). Kiedy termin „złożoność” jest używany bez dalszego definiowania, bierze się pod uwagę najgorszy przypadek złożoności czasowej.

Złożoność w najgorszym i średnim przypadku jest niezwykle trudna do prawidłowego obliczenia. Co więcej, te dokładne wartości mają niewielkie zastosowanie praktyczne, ponieważ jakakolwiek zmiana w maszynie lub paradygmacie obliczeń nieznacznie zmieniłaby złożoność. Co więcej, wykorzystanie zasobów nie jest ważne dla małych wartości n, dlatego łatwość implementacji jest często bardziej atrakcyjna niż niska złożoność dla małych n.

Z tych powodów najwięcej uwagi poświęca się zachowaniu złożoności dla wysokiego n, to jest jej zachowaniu asymptotycznemu, gdy n zbliża się do nieskończoności. W rezultacie duża notacja O jest powszechnie używana do wskazania złożoności.

Modele obliczeniowe

Przy określeniu złożoności istotny jest wybór modelu obliczeniowego, który polega na określeniu podstawowych operacji wykonywanych w jednostce czasu. Czasami nazywa się to wielotaśmową maszyną Turinga, jeśli paradygmat obliczeń nie jest szczegółowo opisany.

Deterministyczny model obliczeń to taki, w którym kolejne stany maszyny i operacje do wykonania są całkowicie określone przez stan poprzedni. Funkcje rekurencyjne, rachunek lambda i maszyny Turinga były pierwszymi modelami deterministycznymi. Maszyny o dostępie swobodnym (znane również jako maszyny RAM) są popularnym paradygmatem symulacji komputerów w świecie rzeczywistym.

Gdy model obliczeniowy nie jest zdefiniowany, zwykle zakłada się wielotaśmową maszynę Turinga. Na wielotaśmowych maszynach Turinga złożoność czasowa jest taka sama jak na maszynach z pamięcią RAM w przypadku większości algorytmów, chociaż może być wymagana znaczna uwaga w sposobie przechowywania danych w pamięci, aby osiągnąć tę równoważność.

Na niektórych etapach obliczeń można dokonać różnych wyborów w niedeterministycznym modelu obliczeniowym, takim jak niedeterministyczne maszyny Turinga. W teorii złożoności wszystkie możliwe opcje są rozważane w tym samym czasie, a niedeterministyczna złożoność czasowa to ilość czasu wymagana, aby zawsze dokonywać najlepszych wyborów. Innymi słowy, obliczenia są wykonywane jednocześnie na tylu (identycznych) procesorach, ile jest wymaganych, a niedeterministyczny czas obliczeń to czas, w którym pierwszy procesor wykonuje obliczenia. Ten paralelizm może być wykorzystany w obliczeniach kwantowych poprzez użycie nałożonych stanów splątanych podczas uruchamiania wyspecjalizowanych algorytmów kwantowych, takich jak na przykład faktoryzacja Shora małych liczb całkowitych.

Nawet jeśli taki model obliczeniowy nie jest obecnie wykonalny, ma on znaczenie teoretyczne, szczególnie w odniesieniu do problemu P = NP, który pyta, czy klasy złożoności utworzone przy użyciu „czasu wielomianu” i „czasu wielomianu niedeterministycznego” jako najmniej granice są takie same. W komputerze deterministycznym symulacja algorytmu NP wymaga „czasu wykładniczego”. Jeśli zadanie można rozwiązać w czasie wielomianowym w układzie niedeterministycznym, należy ono do klasy trudności NP. Jeśli problem jest NP i nie jest łatwiejszy niż jakikolwiek inny problem NP, mówi się, że jest NP-zupełny. Problem plecakowy, problem komiwojażera i problem spełnialności Boole'a to wszystkie problemy kombinatoryczne NP-zupełne. Najbardziej znany algorytm ma złożoność wykładniczą dla wszystkich tych problemów. Gdyby którekolwiek z tych zagadnień można było rozwiązać w czasie wielomianowym na maszynie deterministycznej, to wszystkie problemy NP mogłyby być również rozwiązane w czasie wielomianowym i ustalono by P = NP. Od 2017 r. powszechnie przyjmuje się, że P NP, co oznacza, że ​​najgorsze sytuacje problemów NP są zasadniczo trudne do rozwiązania, tj. trwają znacznie dłużej niż jakikolwiek możliwy przedział czasu (dziesiątki) przy interesujących długościach wejściowych.

Obliczenia równoległe i rozproszone

Przetwarzanie równoległe i rozproszone obejmuje dzielenie przetwarzania na wiele procesorów, które działają w tym samym czasie. Podstawowym rozróżnieniem pomiędzy różnymi modelami jest sposób przesyłania danych pomiędzy procesorami. Transmisja danych między procesorami jest zwykle bardzo szybka w przypadku obliczeń równoległych, podczas gdy przesyłanie danych między procesorami w obliczeniach rozproszonych odbywa się przez sieć, a zatem jest znacznie wolniejsze.

Obliczenia na N procesorach zajmują co najmniej iloraz N czasu, jaki zajmuje pojedynczy procesor. W rzeczywistości, ponieważ niektóre podzadania nie mogą być zrównoleglone, a niektóre procesory mogą potrzebować czekać na wynik z innego procesora, ta teoretycznie idealna granica nigdy nie zostanie osiągnięta.

Kluczową kwestią złożoności jest więc opracowanie algorytmów tak, aby iloczyn czasu obliczeń przez liczbę procesorów był jak najbardziej zbliżony do czasu wymaganego do wykonania tych samych obliczeń na pojedynczym procesorze.

Obliczenia kwantowe

Komputer kwantowy to komputer z modelem obliczeniowym opartym na mechanice kwantowej. Teza Churcha-Turinga jest prawdziwa dla komputerów kwantowych, sugerując, że każdy problem, który komputer kwantowy może rozwiązać, może być również rozwiązany przez maszynę Turinga. Jednak niektóre zadania można teoretycznie rozwiązać za pomocą komputera kwantowego, a nie klasycznego komputera o znacznie mniejszej złożoności czasowej. Na razie jest to czysto teoretyczne, bo nikt nie wie, jak zbudować praktyczny komputer kwantowy.

Teoria złożoności kwantowej została stworzona w celu zbadania różnych rodzajów problemów, które mogą być rozwiązywane przez komputery kwantowe. Jest on wykorzystywany w kryptografii post-kwantowej, czyli w procesie tworzenia protokołów kryptograficznych odpornych na ataki komputerów kwantowych.

Złożoność problemu (dolne granice)

Sednem złożoności algorytmów, które mogą rozwiązać problem, w tym nieodkrytych technik, jest złożoność problemu. W rezultacie złożoność problemu jest równa złożoności dowolnego algorytmu, który go rozwiązuje.

W rezultacie każda złożoność podana w dużym notacji O reprezentuje złożoność zarówno algorytmu, jak i towarzyszącego mu problemu.

Z drugiej strony uzyskanie nietrywialnych dolnych granic złożoności problemu jest często trudne i istnieje niewiele strategii, aby to zrobić.

Aby rozwiązać większość problemów, wszystkie dane wejściowe muszą zostać odczytane, co zajmuje czas proporcjonalny do wielkości danych. W rezultacie takie problemy mają co najmniej liniową złożoność lub, w notacji big omega, złożoność Ω(n).

Niektóre problemy, takie jak te z algebry komputerowej i obliczeniowej geometrii algebraicznej, mają bardzo duże rozwiązania. Ponieważ dane wyjściowe muszą być zapisane, złożoność jest ograniczona przez maksymalny rozmiar danych wyjściowych.

Liczba porównań wymaganych przez algorytm sortowania ma nieliniową dolną granicę Ω(nlogn). W rezultacie najlepsze algorytmy sortowania są najbardziej wydajne, ponieważ ich złożoność wynosi O(nlogn). Fakt, że nie ma n! sposoby organizowania n rzeczy prowadzą do tej dolnej granicy. Ponieważ każde porównanie dzieli ten zbiór n! zamówień na dwie części, liczba N porównań wymaganych do rozróżnienia wszystkich zamówień musi wynosić 2N > n!, co implikuje O(nlogn) według wzoru Stirlinga.

Redukcja problemu do innego problemu jest powszechną strategią uzyskiwania ograniczeń o zmniejszonej złożoności.

Rozwój algorytmu

Ocena złożoności algorytmu jest ważnym elementem procesu projektowania, ponieważ dostarcza użytecznych informacji o wydajności, której można się spodziewać.

Częstym nieporozumieniem jest to, że w wyniku prawa Moore'a, które przewiduje wykładniczy wzrost mocy nowoczesnych komputerów, ocena złożoności algorytmów stanie się mniej istotna. Jest to błędne, ponieważ zwiększona moc pozwala na przetwarzanie ogromnych ilości danych (big data). Na przykład każdy algorytm powinien działać poprawnie w czasie krótszym niż sekundę podczas sortowania alfabetycznie listy kilkuset wpisów, takich jak bibliografia książki. Z drugiej strony, dla miliona wpisów (na przykład numerów telefonów dużego miasta), podstawowe algorytmy wymagające porównań O(n2) musiałyby wykonać bilion porównań, co zajęłoby trzy godziny z prędkością 10 miliony porównań na sekundę. Z drugiej strony sortowanie szybkie i sortowanie przez scalanie wymagają jedynie porównań typu nlogn (jako złożoność przeciętnego przypadku dla pierwszego, jako złożoność najgorszego przypadku dla drugiego). Daje to około 30,000,000 1,000,000 3 porównań dla n = 10 XNUMX XNUMX, co zajęłoby tylko XNUMX sekundy przy XNUMX milionach porównań na sekundę.

W rezultacie ocena złożoności może pozwolić na wyeliminowanie wielu nieefektywnych algorytmów przed wdrożeniem. Można to również wykorzystać do dostrojenia złożonych algorytmów bez konieczności testowania wszystkich możliwych wariantów. Badanie złożoności pozwala skoncentrować wysiłek na zwiększeniu wydajności implementacji poprzez określenie najbardziej kosztownych kroków złożonego algorytmu.