Witam,
Mam mały problem, mianowicie - muszę wyszukać maksymalną wartość w zbiorze liczb, w C++. Wiadomo, można to rozwiązać za pomocą pętli (wyszukiwanie liniowe), jednak takie wyszukiwanie jest nieefektywne. Czy istnieje jakiś algorytm, pozwalający szybko wyszukać taką wartość? A jeśli tak, mógłby mi ktoś go wytłumaczyć/zapodać jakiegoś linka?
Z góry dzięki, i przepraszam, jeśli wybrałem zły dział
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
-
- Użytkownik
- Posty: 132
- Rejestracja: 1 cze 2012, o 07:04
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 15 razy
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
bez dodatkowych założeń musisz przejrzeć wszystkie liczby (bo może ta następna jest większa)
- Althorion
- Użytkownik
- Posty: 4541
- Rejestracja: 5 kwie 2009, o 18:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 9 razy
- Pomógł: 662 razy
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
Jak ksisquare napisał, klasyczny algorytm deterministyczny musi przeszukać wszystkie liczby w najgorszym przypadku.
Dla algorytmów kwantowych istnieje jednak , który z prawdopodobieństwem nie gorszym niż \(\displaystyle{ 1 - \frac{1}{2^c}}\) znajdzie maksimum w czasie \(\displaystyle{ O(c\sqrt{n})}\), gdzie \(\displaystyle{ n}\) to długość przeszukiwanej tablicy.
Dla algorytmów kwantowych istnieje jednak , który z prawdopodobieństwem nie gorszym niż \(\displaystyle{ 1 - \frac{1}{2^c}}\) znajdzie maksimum w czasie \(\displaystyle{ O(c\sqrt{n})}\), gdzie \(\displaystyle{ n}\) to długość przeszukiwanej tablicy.
-
- Użytkownik
- Posty: 5
- Rejestracja: 10 lip 2012, o 08:13
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 4 razy
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
OK. Skoro kod
Realizuje wyszukiwanie liniowe, to jakie jest wyszukiwanie nieliniowe, i jak wyglądałby przy tym kod?
@Althorion, a co to jest algorytm kwantowy? Przepraszam, ale w gimnazjum nas tego nie uczyli
Zresztą, co by nie mówić... Kompletnie nie rozumiem tego linku, który podałeś Nie ze względu na angielski, ale ze względu na wzory, których znaczenia nie znam.
Właściwie chodzi mi o to, aby gdy mam tablicę n liczb, to aby jak najszybciej znaleźć wartość największą z tych n liczb
Kod: Zaznacz cały
int l = 0;
max_wartosc = tablica_licznikow[ 0 ];
while( liczba_licznikow != l )
{
l++;
if( tablica_licznikow[ l ] > max_wartosc )
{
max_wartosc = tablica_licznikow[ l ];
}
}
@Althorion, a co to jest algorytm kwantowy? Przepraszam, ale w gimnazjum nas tego nie uczyli
Zresztą, co by nie mówić... Kompletnie nie rozumiem tego linku, który podałeś Nie ze względu na angielski, ale ze względu na wzory, których znaczenia nie znam.
Właściwie chodzi mi o to, aby gdy mam tablicę n liczb, to aby jak najszybciej znaleźć wartość największą z tych n liczb
- steal
- Użytkownik
- Posty: 1043
- Rejestracja: 7 lut 2007, o 18:35
- Płeć: Mężczyzna
- Lokalizacja: Białystok|Warszawa
- Podziękował: 6 razy
- Pomógł: 160 razy
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
Nie zawracaj sobie głowy algorytmem kwantowym, na razie nie ma maszyn na których go uruchomisz.
Tak jak powiedział jeden z przedmówców, jeżeli masz tablicę z losowo ustawionymi wartościami to musisz sprawdzić wszystkie elementy tej tablicy by mieć pewność, że wybrałeś element o wartości maksymalnej. Natomiast gdybyś miał tą tablicę posortowaną malejąco (element o maksymalnej wartości byłby na pierwszym miejscu w tablicy, a każdy kolejny byłby mniejszy lub równy od poprzedniego) to nie ma potrzeby przejścia wszystkich elementów, bo ten pierwszy jest tym szukanym.
Tak jak powiedział jeden z przedmówców, jeżeli masz tablicę z losowo ustawionymi wartościami to musisz sprawdzić wszystkie elementy tej tablicy by mieć pewność, że wybrałeś element o wartości maksymalnej. Natomiast gdybyś miał tą tablicę posortowaną malejąco (element o maksymalnej wartości byłby na pierwszym miejscu w tablicy, a każdy kolejny byłby mniejszy lub równy od poprzedniego) to nie ma potrzeby przejścia wszystkich elementów, bo ten pierwszy jest tym szukanym.
-
- Użytkownik
- Posty: 5
- Rejestracja: 10 lip 2012, o 08:13
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 4 razy
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
hmm dobra, trudno. To temat można już zamknąć.
PS. Zna ktoś jakąś fajną stronkę odnośnie algorytmiki, tylko nie takiej bardzo zaawansowanej? Jeśli tak, piszcie tutaj/na PW. Będę wdzięczny
//edit:
@steal, dzięki, aczkolwiek tą stronkę znam Jakieś inne może?
PS. Zna ktoś jakąś fajną stronkę odnośnie algorytmiki, tylko nie takiej bardzo zaawansowanej? Jeśli tak, piszcie tutaj/na PW. Będę wdzięczny
//edit:
@steal, dzięki, aczkolwiek tą stronkę znam Jakieś inne może?
Ostatnio zmieniony 10 lip 2012, o 12:34 przez math12345, łącznie zmieniany 1 raz.