[Algorytmika] rosnacy segment w tablicy

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

[Algorytmika] rosnacy segment w tablicy

Post autor: leg14 » 14 paź 2017, o 13:53

Powiedzmy ze mam tablice n- elementowa i chce sprawdzic, czy jest w niej segment 3 rosnacych wartosci (powiedzmy, ze nie musza rosnac ostro).
Ja to robie tak:

Kod: Zaznacz cały


int funkcja (int tab, int lewy ) {

int w ;

w = znajdzrosnacy(tab, lewy);

if (w >= n) then return false;

else if (tab[w+1] >=tab[w]) return true;

else return funkcja(tab,w+1);

}



(funkcja znajdz rosnacy szuka w tablicy (poczynajac od elementu tab[lewy]) pierwszego elementu wiekszego od poprzedniego i zwraca jego wspolrzedna).
Da sie to zrobic szybciej?
Ostatnio zmieniony 14 paź 2017, o 23:09 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Algorytmika] rosnacy segment w tablicy

Post autor: Afish » 15 paź 2017, o 01:24

Jeżeli to ma złożoność liniową(a na oko ma), to nie da się.

ODPOWIEDZ