Strona 1 z 1
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 24 lut 2015, o 22:53
autor: kirk1994
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?
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 24 lut 2015, o 23:43
autor: Gouranga
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)}\)
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 25 lut 2015, o 08:07
autor: kirk1994
Myślę , że złożoność = ilość porównań w czasie wykonywania.
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 25 lut 2015, o 09:21
autor: Gouranga
No czyli złożoność czasowa. Jest tez złożoność pamięciowa.
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 25 lut 2015, o 10:18
autor: Vardamir
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)}\)
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 25 lut 2015, o 17:53
autor: kirk1994
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ń
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 25 lut 2015, o 18:42
autor: Vardamir
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.
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 25 lut 2015, o 19:31
autor: kirk1994
No to pokaż , jak z 6 elementowego zbioru wychodzi 9 porównań.
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 26 lut 2015, o 11:52
autor: Vardamir
\(\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
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 26 lut 2015, o 12:07
autor: bartek118
Przecież to jest algorytm liniowy \(\displaystyle{ O(n)}\) i tyle. Dokładnie jakby policzyć to wychodzi \(\displaystyle{ \frac{3n}{2}}\)
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 26 lut 2015, o 15:21
autor: Vardamir
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.
[Algorytmy] Wyszukiwanie minimum i maksimum w ciągu
: 26 lut 2015, o 18:59
autor: bartek118
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