[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu

kirk1994 · Post autor: **kirk1994** » 24 lut 2015, o 22:53

Równoczesne wyszukiwanie minimum i maksimum w ciagu \(\displaystyle{ n}\) elementowym mozna zrealizowac
ustawiajac elementy ciagu w pary, a nastepnie wybierajac element najmniejszy z mniejszych
elementów par i element najwiekszy - z wiekszych elementów par. Jezeli dodatkowo \(\displaystyle{ n}\) jest nieparzyste,
to nalezy porównac otrzymane elementy z ostatnim, który nie ma pary.
a) Jaki jest koszt tego algorytmu, jesli ciag ma \(\displaystyle{ 6}\) elementów?
b) Jaki jest koszt tego algorytmu, jesli ciag ma \(\displaystyle{ 9}\) elementów?
c) Jaki jest koszt w przypadku, gdy ciag ma \(\displaystyle{ n}\) elementów oraz \(\displaystyle{ n}\) jest liczba parzysta?
d) Czy koszt tego algorytmu jest liniowy?

Gouranga · Post autor: **Gouranga** » 24 lut 2015, o 23:43

Nie wiadomo o jaki koszt (czy formalniej mówiąc o jaką złożoność chodzi). Jeśli o czasową to jest \(\displaystyle{ O(\log n)}\)

kirk1994 · Post autor: **kirk1994** » 25 lut 2015, o 08:07

Myślę , że złożoność = ilość porównań w czasie wykonywania.

Gouranga · Post autor: **Gouranga** » 25 lut 2015, o 09:21

No czyli złożoność czasowa. Jest tez złożoność pamięciowa.

Vardamir · Post autor: **Vardamir** » 25 lut 2015, o 10:18

Gouranga pisze:Jeśli o czasową to jest \(\displaystyle{ O(\log n)}\)

Jak Ci to wyszło? Dla sześciu elementów, ten algorytm wykona dziewięć porównań. Ogólny przypadek to \(\displaystyle{ \left\lfloor \frac{n}{2} \right\rfloor + 2 \cdot \left\lfloor \frac{n}{2} \right\rfloor + 2\cdot \left( n-2\cdot \left\lfloor \frac{n}{2} \right\rfloor \right)}\) porównań.
Kolejno - na ustawienie w parach, na wyszukanie minimum i na wyszukanie maksimum, na uwzględnienie dodatkowego elementu.

Zatem złożoność to \(\displaystyle{ O(n)}\)

kirk1994 · Post autor: **kirk1994** » 25 lut 2015, o 17:53

Jakim cudem jeżeli \(\displaystyle{ 6}\) elementów to \(\displaystyle{ 9}\) porównań .
Weźmy tablice \(\displaystyle{ [5\ 8\ 1\ 3\ 6\ 2]}\)

Układamy w pary : \(\displaystyle{ [5\ 8]\ [1\ 3]\ [6\ 2]}\) i porównujemy --> \(\displaystyle{ 3}\) porównania
Wychodzi nam znowu \(\displaystyle{ [5\ 1\ 2]\ [8\ 3\ 6]}\) i znowu w pary
Czyli \(\displaystyle{ [5\ 1]}\) zostaje \(\displaystyle{ 2}\) i \(\displaystyle{ [8\ 3]}\) zostaje \(\displaystyle{ 6}\) --> \(\displaystyle{ 2}\) porownania
Musimy porównać te elementy co zostały z tymi co wyszły : \(\displaystyle{ [1\ 2]}\) i \(\displaystyle{ [8\ 6]}\) --> \(\displaystyle{ 2}\) porównania
\(\displaystyle{ 3+2+2 = 7}\) porównań

Vardamir · Post autor: **Vardamir** » 25 lut 2015, o 18:42

kirk1994 pisze:Wychodzi nam znowu [5 1 2] [8 3 6] i znowu w pary

Dlaczego znowu w pary, gdzie w twoim opisie algorytmu jest coś takiego napisane? W tym momencie, spośród elementów mniejszych szukasz najmniejszego, każdy porównując z aktualnym minimum. To samo dla największego.

kirk1994 · Post autor: **kirk1994** » 25 lut 2015, o 19:31

No to pokaż , jak z 6 elementowego zbioru wychodzi 9 porównań.

Vardamir · Post autor: **Vardamir** » 26 lut 2015, o 11:52

\(\displaystyle{ [5\ 8\ 1\ 3\ 6\ 2]}\)
Ustawiamy je w pary mniejsza-większa. (trzy porównania)

\(\displaystyle{ [5\ 8\ 1\ 3\ 2\ 6]}\)
Nie jest sprecyzowane w poleceniu, jakie jest \(\displaystyle{ n}\). Przyjmuje, że dowolne całkowite.

Niech \(\displaystyle{ \min=-\infty}\) oraz \(\displaystyle{ \max=\infty}\).

Teraz \(\displaystyle{ \min}\) porównujemy z pozycjami nieparzystymi (trzy porównania), natomiast \(\displaystyle{ \max}\) z pozycjami parzystymi (trzy porównania).

Można na początku przyjąć za \(\displaystyle{ \min}\), \(\displaystyle{ \max}\) odpowiednio pierwszy i drugi element ciągu, wówczas odpadną dwa porównania. Jednak to zależy od tego jak realizujemy początkowy stan wyszukiwania najmniejszego/największego elementu

bartek118 · Post autor: **bartek118** » 26 lut 2015, o 12:07

Przecież to jest algorytm liniowy \(\displaystyle{ O(n)}\) i tyle. Dokładnie jakby policzyć to wychodzi \(\displaystyle{ \frac{3n}{2}}\)

Vardamir · Post autor: **Vardamir** » 26 lut 2015, o 15:21

Oczywiście, że jest liniowy. Do tego zmierzamy.

bartek118 pisze:Dokładnie jakby policzyć to wychodzi \(\displaystyle{ \frac{3n}{2}}\)

Dokładnie to raczej nie. \(\displaystyle{ n=3}\) daje \(\displaystyle{ 4,5}\) porównania.

bartek118 · Post autor: **bartek118** » 26 lut 2015, o 18:59

Vardamir pisze:Oczywiście, że jest liniowy. Do tego zmierzamy.
bartek118 pisze:Dokładnie jakby policzyć to wychodzi \(\displaystyle{ \frac{3n}{2}}\)
Dokładnie to raczej nie. \(\displaystyle{ n=3}\) daje \(\displaystyle{ 4,5}\) porównania.

Dla \(\displaystyle{ n}\) parzystych