Co oznacza pamięć Θ (1)?

Mam definicję algorytmu in-situ od profesora, ale nie rozumiem tego.

Algorytmy in-situ odnoszą się do algorytmów działających z pamięcią Θ (1).

Co to znaczy?

algorithms terminology landau-notation

— zeeks
źródło

Czy znasz notację Landaua ?

— David Richerby

„Mówi się, że algorytm jest algorytmem in situ lub algorytmem na miejscu, jeżeli dodatkowa ilość pamięci wymagana do wykonania algorytmu wynosi O (1), to znaczy [pamięć] nie przekracza stałej bez względu na to, jak duża dane wejściowe . Na przykład heapsort jest algorytmem sortowania na miejscu. ” en.wikipedia.org/wiki/In_situ#Computer_science

— Auberon

@Auberon, należy dodać, że

nakłada dodatkowy wymóg niż

: że całkowita pamięć używana w jakimkolwiek konkretnym wywołaniu nie spada poniżej stałej bez względu na wielkość danych wejściowych.

Θ (1)

$\Theta(1)$

O (1)

$O(1)$

— Olathe

@Olathe Nie widziałem jeszcze algorytmu, który wykorzystuje więcej niż zero, ale mniej niż stałą dowolnego zasobu

— adrianN

@adrianN, szyfrowanie plików AES odbywa się przy użyciu pamięci RAM w stałej górnej granicy. Przetwarzasz blok naraz, każdy blok wymaga przetworzenia tej samej ilości pamięci RAM, a pamięć RAM może być ponownie użyta z jednego bloku do drugiego. Prostszym przykładem jest konwersja wszystkich liter w pliku zakodowanym w ASCII na wielkie litery. Możesz odczytać plik, powiedzmy 4096 bajtów, przetworzyć ten 4096 bajtów, zapisać wyniki tego bloku i ponownie użyć tej samej pamięci RAM dla następnego bloku.

— Olathe

Odpowiedzi:

$\Theta(1)$

$O$ $\Theta$ $f$ $O(1)$ $c$ $x$ $f(x) \leq C$ $f$

$\Theta$ $f \in \Theta(1)$ $c,d$ $x$ $d \leq f(x) \leq c$ $f$

$A$ $n$ $A$ $n$ $mem$

$\Theta(1)$ $\Theta(1)$ $d,c$ $d$ $c$

Krótko mówiąc, oznacza to, że użycie pamięci algorytmu jest w pewnym stałym zakresie, niezależnie od danych wejściowych.

$\Theta(n)$

— jmite
źródło

„nie zależy skutecznie od jego wkładu”. - dla której definicji „skutecznie”?

— Raphael

Podobnie jak w, używana pamięć może się zmieniać w zależności od danych wejściowych, ale tylko w określonym przedziale czasowym. Możesz go edytować, jeśli możesz wymyślić lepsze sformułowanie.

— jmite

d

$d$

c

$c$

pomocny byłby prosty przykład ilustrujący

— wer

Stała złożoność algorytmu w przestrzeni

Ilość pamięci wykorzystywanej przez algorytm jest niezależna od danych wejściowych.

$10$ $10$

Jednak algorytmy In-situ wykonują zamierzoną funkcję na samym wejściu, a zatem wymagają bardzo mało lub nie wymagają dodatkowej przestrzeni. Dane wejściowe są zwykle nadpisywane przez dane wyjściowe podczas wykonywania algorytmu. ( ref )

Algorytmy in-situ nie uwzględniają przestrzeni zajmowanej przez dane wejściowe i uwzględniają tylko dodatkową przestrzeń, obliczając złożoność przestrzeni.

— Prateek
źródło

Θ (1)

$\Theta(1)$

@Olathe Przestrzeń zajmowana przez każde wejście pod względem bajtów i liczba danych wejściowych pod względem liczby nie są dwiema różnymi koncepcjami?

— Prateek

Oznacza to, że dodatkowa ilość pamięci wymagana dla algorytmu nie jest większa niż pewna stała ilość, która nie zależy od wielkości wejścia dla wystarczająco dużego wejścia.

— Somnium
źródło

Θ

$\Theta$

O

$O$

Ω

$\Omega$

O (x^{2})

$O(x^2)$

f (x) = 3 x^{2}

$f(x) = 3x^2$

f (x) = x

$f(x) = x$

Θ (x^{2})

$\Theta(x^2)$

f (x) = 3 x^{2}

$f(x) = 3x^2$

f (x) = x

$f(x) = x$