Algorytmy - materiały do rozwiązania zadań

Cześć, czy jest tu ktoś kto ma materiały które tłumaczą jak rozwiązać tego typu zadania?
Chodzi tutaj o matematyczne wyliczanie funkcji. Trzeba 'dojść' do rozwiązania.
Tak samo w kwestii szukania złożoności danego algorytmu - posiada ktoś materiały które tłumaczą step-by-step jak wyliczyć złożonoścćalgorytmu?

W drugim, pesymistyczna złożoność, to będzie ~log2(z) - 1 - za każdym obiegiem pętli, dzielimy w integerach z przez dwa, czyli logarytm i na pewno jedna z liczb będzie parzysta, stąd minus jeden.

Jeśli możesz skorzystać z Wolframa, to formuła do pierwszego może wyglądać tak: sum(sum(sum(1) from k=1 to j) from j=i+1 to n) from i=1 to n-1. Wolfram wyrzuca n(n^2-1)/3. Ręcznie trzeba by było po prostu wiele razy zastosować wzory na sumę kolejnych liczb, kwadratów, sześcianów, ale to od groma liczenia. Wynik wydaje się być poprawny:

public static void Main()
{
    var n = 10;
    var r = 0;
    for (var i = 1; i <= n - 1; i++)
    {
        for (var j = i + 1; j <= n; j++)
        {
            for (var k = 1; k <= j; k++)
            {
                r = r + 1;	
            }
        }
    }
    Console.WriteLine(r); // 330
    Console.WriteLine(n * (n * n - 1) / 3 ); // 330
}

Chociaż pewnie można jakoś prosto to zrobić. Np. policzyć, że f(n+1)=f(n)+n(n+1), po zrobieniu czegoś podobnego do tego: https://cs.stackexchange.com/questions/43434/how-to-solve-tn-tn-1-n2 dostalibyśmy sumę i(i+1) from i=1 to n-1, a to już ze wzoru na sumę kolejnych liczb i kwadratów.

to jaka to jest złożoność itd jestem w stanie stwierdzić... chodzi o to żę wykładowca własnie wymaga recznego wyprowadzenia tego wszystkiego, a ja szukam materiałów które w jakis dobry sposób tlumacza analize alogrytmów;x

To mu Wylicz ręcznie, że w drugim przypadku, w najgorszym wypadku będzie log2z - 1, , np, mnoz(3, 30), da cztery wykonania dodawania (więcej nie może być, bo zawsze musi być jedna liczba parzysta).

@lion137: byłoby pięknie gdyby takie coś przeszło wtedy nawet tego tematu bym nie zakładał. Niestety jestem złej myśli żę to jeden z tych wykładowców który będzie wymagał tego w taki sposób jak on pokazywał, czyli wyprowadzanie wszystkiego od 0...

swoją drogą.. tutaj:

zlozonosc bedzie O(logz), a jak z ta wartoscia przy pesymistycznym przypadku?

W pesymistycznym przypadku będzie dokładnie log2(z) - 1 dodawań; tak jak podałem, np., dla z = 30.

lion137 napisał(a):

W pesymistycznym przypadku będzie dokładnie log2(z) - 1 dodawań; tak jak podałem, np., dla z = 30.

no w zadaniu 4 to raczej mnozen :D

tutaj mala wrzutka przykladowych notatek z rozwiazania zadania 2giego.
srednio sie potrafie w tym polapac, ale moze tobie wydaje sie to znajome i znasz kojarzysz jakies materialy ktore to jakos tlumacza?

Po co prosta rzecz zamieniać w bełkot :), jesli w każdym obiegu pętli z dzieli się przez 2, to ilośc operacji jest proporcjonalna do logarytmu przy podstawie dwa z z, i, w pesymitycznym przypadku taich liczb nieparzystych będzie log2(z) - 1 - bo co najmniej jedna będzie parzysta, jak w przypadku z= 30.