Złożoność czasowa dodawania

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

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)$

algorithms algorithm-analysis arithmetic

— Tobi Alafin
źródło

Odpowiedzi:

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. $n$ $\mathcal{O}(\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 . $\frac{n}{32}$ $\mathcal{O}(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?

a

$a$

b, a : a \geq b, a + b \leq 2 a

$b, a: a \ge b, a + b \le 2a$

2 a

$2a$

O (1)

$O(1)$

0

$0$

n

$n$

— Tobi Alafin

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

$2a$

2 a

$2a$

O (1)

$O(1)$

0

$0$

O (\log (n))

$O(\log(n))$

a

$a$

O (n)

$O(n)$

a

$a$

2 a

$2a$

— Lieuwe Vinkhuijzen,

Mam algorytm, który znajduje długość

. Wykorzystuje wyszukiwanie binarne.

a

$a$

O (\log n)

$O(\log n)$

— Tobi Alafin

@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

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ć

. Załóżmy, że nie, a na wejściu z

bitów, nie sprawdza się

-tego bitu. Wtedy mógłbym to przerzucić, a to dałoby złą odpowiedź.

O (\log n)

$O(\log n)$

O (n)

$O(n)$

a + b

$a+b$

42

$42$

6

$6$

— Lieuwe Vinkhuijzen,

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)

$\Omega(n)$

— Bakuriu

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 . $\Theta(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. $\Theta(|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

Θ (\log n)

$\Theta(\log n)$

n

$n$

$\Omega(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

$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