Strona 1 z 1
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
: 10 lip 2012, o 08:20
autor: math12345
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
: 10 lip 2012, o 10:49
autor: ksisquare
bez dodatkowych założeń musisz przejrzeć wszystkie liczby (bo może ta następna jest większa)
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
: 10 lip 2012, o 10:57
autor: Althorion
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.
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
: 10 lip 2012, o 11:12
autor: math12345
OK. Skoro kod
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 ];
}
}
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
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
: 10 lip 2012, o 12:11
autor: steal
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.
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
: 10 lip 2012, o 12:22
autor: math12345
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?
[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości
: 10 lip 2012, o 12:25
autor: steal