Forum 1 Grupy Ćwiczeniowej

dyrek_87

No więc jak każdy wie jutro koło ktokolwiek cokolwiek ma coś przydatnego to prosiłbym sie dzielić i wrzucać. Szczególnie to chodzi mi o zadanka dwa z I koła które mają być na kole jak ktoś może rozkmini je to niech wrzuci tyle ode mnie Wink

inni pewnie też sie dołączą do prośby Smile

ps. Daniel(Dudi) mówił że rozkmini więc czekamy Wink

[/img]

Dudi

hehe, "Daniel mówił że rozkmini" ;p mówiłem tylko że spróbuje, zaraz usiąde, bo wczoraj cały dzień u dziewczyny przebimbałem

dyrek_87

"spróbuje" ... nie bądz taki skromny Razz

Dudi

Zad 2, Rząd 1, z zadanek:
[link widoczny dla zalogowanych]

Ta większa pętla (i>=1) wykona się od i = 2^t do i = 2^0, w kolejnych krokach bedzie i = 2^(t-1), i = 2^(t-2) itd, czyli t+1 razy, bo te "i" zmienia się tylko w jednym miejscu i w ten sam sposob (dzili sie przez dwa) raz w kazdej petli.

Mniejsza pętla (p<=k) za każdym razem będzie wykonywała się tyle samo razy, bo jest niezależna od "i". "m" jest srodkiem odcinka [p, k], zaokrąglany w dół do całości (bo to liczby całkowite), więc zawsze ta druga połowa odcinka(gdzie za poczatek podstawiamy m -> [m, k] ) bedzie większa (albo równa), czyli gdy warunek ifa bedzie spelniony. Stąd przypadek pesymistyczny bedzie gdy zawsze bedzie spełniony warunek if (A[m]<x). Ta pętla wykona się t+1 razy (wywnioskowane z przykładów) i w każdej będzie jedna operacja porównania.

Razem będzie Tmax = (t+1) * (t+1) = (t+1)^2 = ( log(o podst 2, z n) ) ^2.

Chyba.

Dudi

jeszcze cos zrobie jak wroce, na razie spadam

czart

Na tym kole będą zagadnienia z koła nr 1 i 2 ?

wicher

Chyba tak. Coś mi się wydaje, że mówiła o liczeniu kosztów algorytmów, porównywaniu rzędów funkcji i metoda zachłanna z dynamiczną. Ale być może "wydaje mi się" tylko. No i oczywiście materiał po pierwszym kole.

czart

a sa jutro ćwiczenia ?

fala (aka tomek)

ćwiczeń jako takich nie ma... babka powiedziala ze bedzie w sali na wypadek jakby ktos chcial przyjsc i sie o co jeszcze zapytac

Roberto

Ma ktos moze te rzędy policzone z zadania nr 1?

Dudi

który rząd Roberto?

Roberto

A obojetnie, moze byc pierwszy;-) Chce obadac jak to powinno sie zrobic

fala (aka tomek)

najfajniej to byłoby mieć całe rozwiązanie tego 1szego zadania, tak żeby mieć rozeznanie jak się za to zabrać i żeby np przykładowe rzędy mieć uporządkowane...
ja wiem tyle że to jakoś trzeba przekształcać te wzorki, ale jak to już nie za bardzo Smile

Roberto

glupie pytanie...no ale jak ten glupi ciag zwinac...;/ Daniel czy ktokolwiek inny posiadający rozwiazanie zadania,proszony o jego zamieszczenie Wink

Thrower, kategorie zlozonosci rzędów są w pierwszym wykladzie Koszelew na jej stronce. Chyba to to;-)

Dudi

ciąg ten 1 + 1/4 + 1/9 + ... + 1/n^2? to szereg, zbiega do jedynki, więc f1 = O(1), czyli koszt stały, to będzie funkcja o najniższym koszcie, juz powoli robie, tylko musze przypomniec sobie jaka byla różnica między O a O z kreską w środku