[C++][Algorytmy] Szybkie wyszukiwanie maksymalnej wartości

math12345
Użytkownik
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

Post 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ł
Ostatnio zmieniony 11 lip 2012, o 20:09 przez Afish, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
ksisquare
Użytkownik
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

Post autor: ksisquare »

bez dodatkowych założeń musisz przejrzeć wszystkie liczby (bo może ta następna jest większa)
Awatar użytkownika
Althorion
Użytkownik
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

Post 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.
math12345
Użytkownik
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

Post 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
Awatar użytkownika
steal
Użytkownik
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

Post 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.
math12345
Użytkownik
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

Post 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?
Ostatnio zmieniony 10 lip 2012, o 12:34 przez math12345, łącznie zmieniany 1 raz.
Awatar użytkownika
steal
Użytkownik
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

Post autor: steal »

ODPOWIEDZ