Analiza dwóch podstawoych modeli obliczeniowych, podstawa analizy algorytmów

Trzecia część serii, 1, 2, mam nadzieję, że już ostatnia - tzn. teraz wszyscy powinni to zrozumieć, łącznie ze mną:). Przypomnę komentarze:

msm:

W modelu RAM Maszyny Turinga, rzeczywiście te algorytmy są w pamięci O(logn). Natomiast myśląc w Word RAM modelu (w którym chyba jest łatwiej), mamy zmienne mogące zapisywać integery o rozmiarze wielomianowym (poly(n)) - który jest O(logn) w bitach. W tym modelu zmienne O(1) są równoważne zmiennym O(logn) w modelu pamięci Maszyny Turinga.
No ok, to w takim razie racja (tak jak @shalom zresztą napisał). To zresztą całkiem sensowne modele w praktyce (przynajmniej WordRam, o tym Real RAM nawet nie wiedziałem i wygląda dziwnie), bo mało kiedy n dąży do czegoś większego niż np. 2**64. Tylko wypada taki model ustalić, bo domyślnie zakładam że mówimy o czymś równoważnym maszynie turinga :P.
To ma duże znaczenie, bo gdyby ograniczyć od góry "n" (nawet bardzo dużą wartością), to np. okazałoby się że RSA jest łamalne w czasie stałym (dla pewnej dużej stałej) i trochę bez sensu by było.

Afish:

Jak przyjmiemy, że liczby są ograniczone z góry (i stąd wnioskujemy O(1)), to BFS też będzie w stałej pamieci

msm:

Ten Aleliunasa i reszty jest O(1) space - nie ma znaczenia ile bitów trzeba na 1000t^3, ustalamy, że u i t to dwa integery, powiedzmy 64 bitowe i mamy stałą pamięć; generalnie nie ma znaczenia nawet ilu bitowe, po prostu ograniczone górą.
Ale jasne że ma znaczenie. Podniesienie liczby n do trzeciej potęgi wymaga "zaalokowania" log_2(n3) (czyli O(log(n))) bitów pamięci. Jeśli będziesz korzystał ze stałej ilości pamięci, to od pewnej wielkości grafu (np. 21000) skończy się miejsce i algorytm przestanie działać. Tak, w praktyce 64 bits should be enough for everyone, ale jak już mówimy o matematyce... ;]
Jeśli mi nie wierzysz powiedzmy, cytat z https://en.wikipedia.org/wiki/In-place_algorithm:
In computational complexity theory, the strict definition of in-place algorithms includes all algorithms with O(1) space complexity, the class DSPACE(1). This class is very limited; it equals the regular languages.[2] In fact, it does not even include any of the examples listed above.
We usually consider algorithms in L, the class of problems requiring O(log n) additional space, to be in-place. This class is more in line with the practical definition, as it allows numbers of size n as pointers or indices. This expanded definition still excludes quicksort, however, because of its recursive calls.

I inni, moja wina nie wyjaśniłem z detalami, to teraz.
Mówimy o dwóch modelach obliczeniowych modelu Maszyny Turinga i modelu Word RAM. Przypuśćmy, że mamy algorytm(palindrome check):

s = 1; e = n
while s < e:
    if x[s] != x[e]: return False
    s += 1; e -= 1
return True

x to string o długości n. W modelu Turing Machine złożoność tego algorytmu należy do Θ(n^2), natomiast w Word RAM do Θ(n). Dlaczego? Co to jest model TM? W Maszynie Turinga nie mamy jako takiego RAM - u (jest symulowany), więc nie możemy "wziąć" integera z rejestru - to wymaga pewnej, zleżnej od n ilości operacji, jak również zaalokowanie pamięci. Czyli TM to nie jest taki komputer jakie mamy współcześnie - przynajmniej co do szczegółów nie działa tak samo - dlatego operacje, którym zwyczajowo w analizie dajemy O(1) czas i pamięć, takie jak s= 1; s +=1 czy odzyskanie x[s] elementu w TM nie są stałe, stąd i Θ(n^2).
Podsumowując TM nie może zaalokować jakiegoś ograniczonego rejestru (np. 32 bitowego) w stałym czasie, nie ma również dostępu do nie go w stałym czasie i nie może wykonywać w stałym czasie na nim operacji arytmetycznych. To samo tyczy się pamięci, dla każdej liczby n ptrzebujemy zaalokować log(n) bitów.
Jeszcze pytanie po co te teoretyczne modele? Właśnie po to żeby jak najlepiej odwzorować jakąś rzeczywistośc obliczeniową, co daje nam ramy do analizy algorytmów.

Word RAM model, w tym modelu zakładamy, że mamy pamięć, jako tablicę z natychmiastowym dostępem (nie uwzględnia to cache, co czyni dużą różnicę - ale tam są bardziej skomplikowane modele, jak i równoległości); możemy również deklarować stałe integery (BoundInts), które są wielomianowe w stosunku do wielkości danych: czyli na ogół jest to długość stringa wejściowego (jak powyżej), czy ilość wierzchołków grafu, jak tutaj; możemy je alokować, inkrementować, oraz wykonywać operacje arytmetyczne w O(1), jak również zajmują O(1) pamięci. Tu jest detal, 2^64 starczy nam spokojnie jako ogranicznk pętli po dowolnej realnej długości danych, również musimy zadbać o przepełnienie tych zmiennych. I, co istotne, musimy udowodnić, że te BoundInegers są wielomianowe dla całego działania algorytmu. Mając to udowodnione, możemy spokjnie przyjmować, że wszystkie operacje w palindrom check powyżej, poza samą iteracją są O(1), i cały algorytm jest O(n) time i O(1) space.
A co z, na przykład z operacjami na wiekszych liczbach, było wspominane w komentarzach, np, 2048 bitowych lub większych? Nie możemy powiedzieć, że taką liczbę inkrementujemy w stałym czasie, czy alokujemy w stałej pamieci. Czyli model nie działa? Nie, musimy go tylko odpowiednio stosować, wielkie liczby traktujemy jak stringi i wykonujemy na nich operacje(przynajmniej te najprostsze), jakbyśmy wykonywali działania na kartce papieru, przykładowy algorytm (dodawanie dwóch BigIntów):

add(a, b):
    """liczby w bazie 10, indeksy od 0 do n -1"""
    carry = 0
    for i in range(0, n): # < n    # i, carry BoundIntegers
        col_sum = x[i] + y[i] + carry    # BoundInteger
        z[i] = col_sum mod 10    # pasowało by wczesniej utworzyć tę tablice :)
        carry = (col_sum - z[i]) // 10    # dzielenie w integerach
    z[n] = carry
    return z

Tu też jak widac możeny stosowac model, ale już uważniej (nasze BoundInts - nie mogą być mniejsze niż ilośc cyfr "obsługiwanych" liczb, Java. na przykład, nawet sama ogranicz BigDecimal do 2^32 - 1 miejsc po przecinku - Poprawcie mnie jak jest inaczej:)) i mając odpowiednia reprezentację wielkich liczb.
Czyli finalnie w Word RAM model, jeśli nasze, jak to nazwaliśmy BoundInts, są dla całego algorytmu wielomianowe od długości danych (a tak jest dla wiekszości realnych algorytmów), to możemy je:
deklarować w stałym czasie;
wykonywać operacje arytmetyczne w stałym czasie;
mamy do nich dostęp w stałym czasie;
zajmują stałą pamięć.
Jak dane stają się wieksze to musimy zmienić model, żeby nie mieć magicznych sytuacji, że zrobimy coś co nie wiemy czy TM może w ogóle wykonać, o których pisali @msm, @Shalom i inni.
To tyle, dziękuję za cierpliwośc:)
Źródła:
Internet:-)
http://www.cs.cmu.edu/~15251/
http://theory.cs.princeton.edu/complexity/