Złożoność czasowa dodawania

11

Wikipedia wymienia złożoność czasową dodawania jako , gdzie jest liczbą bitów.nnn

Czy to sztywna teoretyczna dolna granica? Czy to tylko złożoność obecnie najszybszego znanego algorytmu. Chcę wiedzieć, ponieważ złożoność dodawania podkreśla wszystkie inne operacje arytmetyczne i wszystkie algorytmy, które ich używają.

Czy teoretycznie niemożliwe jest uzyskanie algorytmu dodawania działającego w ? Czy jesteśmy związani liniową złożonością dodawania.o(n)

Tobi Alafin
źródło

Odpowiedzi:

17

Jeśli twój algorytm wykorzystuje asymptotycznie mniej niż czasu, to nie ma wystarczająco dużo czasu, aby odczytać wszystkie cyfry dodawanych liczb. Wyobraź sobie, że operujesz bardzo dużymi liczbami (przechowywanymi na przykład w plikach tekstowych 8 MB). Oczywiście dodawania można dokonać bardzo szybko w porównaniu z wartością liczb; działa w czasie , jeśli jest wartością sumy.O ( log ( N ) ) NnO(log(N))N

Nie oznacza to, że możesz trochę przyspieszyć; jeśli twój procesor obsługuje 32 bity dla każdej operacji, wtedy używasz czasu, ale wciąż jest to a nie . O(n)o(n)n32O(n)o(n)

Lieuwe Vinkhuijzen
źródło
Czyta wszystkie dane teoretycznie niezbędne. Aby dowolne dwie liczby i . Obliczanie można wykonać w operacji poprzez przesunięcie. Dołączanie . Rozważ to. Być może nie znajdziesz szybszego oszacowania sumy, dopracuj oszacowanie, aż będzie prawidłowe. W mniej niż operacji? b , a : a b , a + b 2 a 2 a O ( 1 ) 0 nab,a:ab,a+b2a2aO(1)0n
Tobi Alafin
3
Tak, jest to teoretyczna konieczność, ponieważ: każdy bit danych wejściowych jest wykorzystywany w danych wyjściowych w sposób nietrywialny , przy czym przez pojęcie „nietrywialny” mam na myśli, że nie jest to funkcja tożsamości. W twoim przykładzie , czy można obliczyć w czasie zależy od modelu obliczeniowego: jeśli dodanie jest operacją w czasie stałym, to tak. Jeśli masz dostęp do pamięci RAM, potrzebujesz czasu na zapisanie adresu bitu, jeśli znasz już długość , lub jeśli musisz przeczytać wszystkie aby się dowiedzieć. W tym przykładzie wiele bitów wyjściowych to trywialne funkcje bitów wejściowych. 2 a O ( 1 ) 0 O ( log ( n ) ) a O ( n ) a 2 a2a2aO(1)0O(log(n))aO(n)a2a
Lieuwe Vinkhuijzen,
Mam algorytm, który znajduje długość w O ( log n ) . Wykorzystuje wyszukiwanie binarne. aO(logn)
Tobi Alafin
3
@TobiAlafin Jeśli Twój model obsługuje adresowanie pamięci RAM, wyszukiwanie binarne przebiega w krokach , popraw. Na maszynie Turinga iw pliku tekstowym nie załadowanym do pamięci głównej zajmuje to O ( n ) czasu. W obu przypadkach, aby odpowiedzieć na twoje pytanie, z adresowaniem pamięci RAM lub bez, aby przyspieszyć wyszukiwanie, algorytm będzie musiał spojrzeć na wszystkie bity danych wejściowych, aby obliczyć a + b . Załóżmy, że nie, a na wejściu z 42 bitów, nie sprawdza się 6 -tego bitu. Wtedy mógłbym to przerzucić, a to dałoby złą odpowiedź. O(logn)O(n)a+b426
Lieuwe Vinkhuijzen,
1
Zasadniczo wszystkie operacje są , z tego powodu. Jedynym wyjątkiem jest sytuacja, gdy masz do czynienia z uporządkowaną w jakiś sposób strukturą danych: np. Nie musisz odwiedzać całego BST, aby sprawdzić, czy zawiera on określoną wartość, ale jest to prawdą tylko ze względu na niezmienniki, które pochodzą z BST. Ω(n)
Bakuriu
7

Aby analiza złożoności miała jakikolwiek sens formalny, musisz określić formalny model obliczeniowy, w którym wykonywany jest algorytm w obiekcie, lub przynajmniej model kosztów , który określa, jakie są podstawowe operacje i ich koszty.

W większości kontekstów przyjmuje się, że operacje arytmetyczne zabierają czasu. Jest to zwykle uzasadnione, ponieważ interesuje nas złożoność algorytmiczna niezależnie od liczby. Nazywa się to modelem kosztów jednolitych .Θ(1)

Jeśli liczby mogą rosnąć bez ograniczeń lub jesteśmy zainteresowani analizowaniem samych operacji, przyjmuje się, że operacje arytmetyczne mają koszt , proporcjonalny do wielkości nakładu.Θ(|x|)

Czy operacje mogą mieć mniejszy koszt? Być może jednak trzeba formalnie zdefiniować model obliczeniowy, w którym może się to zdarzyć.

szybkie sortowanie
źródło
1
Θ(logn)n
3

Ω(n)

Wyobraź sobie, że Twój algorytm z powodzeniem dodaje 1010100110 i 0010010110 bez odczytu każdego bitu. Aby algorytm mógł dodawać dowolne dane wejściowe, powinienem być w stanie losowo przerzucić dowolny z tych bitów, a algorytm nadal będzie generował poprawne (ale inne) dodanie. Ale jeśli twój algorytm nie odczytuje trochę, to jak mógł stwierdzić, że odwrócone wejście różni się od pierwotnego?

murrdpirate
źródło
n
Absolutnie. Musisz tylko zdefiniować, co w przybliżeniu oznacza w twoim algorytmie. W zależności od tej definicji dodanie dwóch najbardziej znaczących bitów może być przybliżoną sumą, którą można wykonać w czasie o (n) . Kiedy wspominasz o algorytmie „dodawania”, myślę, że wszyscy to rozumiemy, ponieważ odpowiedź musi być dokładna.
murrdpirate