infoarena

http://infoarena.ro/blog/problema-saptamanii-stream

As avea si eu o intrebare: un stream de numere este tot una cu un vector sau un sir?

se foloseste termenul stream in ideea ca il parcurgi secvential.
while (ob.hasNaext()) {
   ob = ob.getNext();
}

Intrebarea mea este legata de memoria O(k) , asta inseamna ca nu pot aloca memorie pentru variabile auxiliare ? (gen min si max din sirul k)

este solutie o(n) ... ? eu doar de o(n log k) stiam ...

@FlorinV: Limita O(k) nu te restrictioneaza la un vector de k elemente. Poti aloca variabile auxiliare.
@crawler: Exista. :)

Mesaj Editat de moderator : Nu da hinturi la astfel de probleme. Fiecare vrea sa se gandeasca singur :P. Chiar daca solutia ta nu era buna nu se stie niciodata cum se poate ajunge la solutia buna plecand de la asta.
Scz :P dar nu era buna in sensu ca depasea memoria sau nu e buna rezolvarea?:D.

cele mai mici k numere trebuie sa fie in vreo ordine in vectorul de k elemente sau oricum?

ok, cred ca oricum, ca daca ar fi sortate, am putea sorta pe toate N in O(N)... :)

Presupun ca solutia asteptata nu este cea cu statistici de ordine.... Se poate pune iteratorul din nou cel de start(ceva de genul sa reiterez prin stream?)?

Banuiesc ca nu poti sa faci asta din moment ce se precizeaza ca streamul are numai metodele getnext() si hasnext().

Notiunea de stream apare la citiri de date si abstractizeaza modul in care poti citi de la diverse surse de date. Poti citi aici interfata input stream-ului din Java:http://java.sun.com/j2se/1.4.2/docs/api/java/io/InputStream.html

Sirul trebuie parcurs o singura data.

Memoria O(k) inseamna ca exista o constanta c astfel ca memoria sa fie mai mica decat c * k oricare ar fi k. Deci poti tine minte oricate siruri de lungime k vrei 100, 1000, un milion, atata timp cat numarul ala e constant si nu variaza cand n sau k cresc.

E putin cam fortata treaba asta...Sa spui ca 1 000 000*k==k.Asa am lua o matrice de [X] [k] unde X e suficient de mare si spunem ca avem mereu memorie constanta.In my opinion  :-s
[L.E] Acum am inteles.Thx:>

Nu spui ca 1 000 000*k==k, ci ca memoria < 1 000 000*k, indiferent de k. Explicatia mai matematica o gasesti si pe wiki:

http://en.wikipedia.org/wiki/Big_O_notation

TIP: citeste pana mai jos, in zona "Matters of notation" , "Orders of common functions" si "Related asymptotic notations".

Cand k tinde la infinit, 1000000 e o valoare nesemnificativa pe langa el :)

Sters de moderator - solutiile se trimit la cosminn at gmail.com. Nu mai postati rezolvari pe forum.