W dniu 2013-05-12 17:14, Vax pisze:
> W dniu 2013-05-12 16:44, bartekltg pisze:
>
>> Nie ja nie rozumiem, tylko Ty masz nieporządek.
>> Deklarowałeś złożność 2^n. (n<=m) a to nie może być osiagniete,
>> jeśli pamiętasz jedną linię. Wtedy masz m*2^n (m>=n)
>> Tylko tyle;)
>
> Właśnie gdy pamiętam jedną linię jest osiągnięte.
> Cała "iteracja wewnętrzna" to nie szukanie rozwiązania, ale jego test.

Nie, pomyśl, ile operacji musisz wykonać, aby znaleźć rozwiązanie
optymalne. Musisz wygenerować _wszystkie_ kombinacje linii
początkowej, i musisz je przetestować (a także zliczyć kliknięcia).
Kandydatów jest 2^n, a dla każdego wykonujesz m operacji (m>=n)


> Jako, że czasochłonność testu jest zależna od rozmiaru danych (w jednym
> wypadku od liczby bitów na każdy bok, w drugim od ich iloczynu) koszt
> testu pominąłem, istotne, że ja mam do przetestowania np. 16 kombinacji
> zamiast np. 65536 (i to zapewne przy większym koszcie testu w druim
> przypadku).

Ale z czym Ty dyskutujesz? Jeśli min (m,n) =4 to opisamy
przezemnie algorytm musi wykonać <=16 testów, bo na 4
wektory 'zerowe'.


>> Zalapalem, ale pisać nie bronię:)
>
> w sąsiedniej gałęzi wątku wyłuszczyłem, mam nadzieję, że wystarczająco?
>
>> Twój alg jest prosty i rzeczywiśćei łątwo go się optymalizuje sprzętowo,
>> ale pisałem to wszytko po to, byś zobaczył, gdzie bardziej
>> zaawansowany algorytm zyskuje przewagę.
>
> "Pominąłeś koszty operacji macierzowych" ;)

Nie. Z nich bierze się owo O((n*m)^3)


>
>> Wyciąłeś to, więc zakładam, że załapałeś.
>
> załapałem, wiem o czym piszesz, ale jestem zwolennikiem wstępnego

No nie wiem, uwaga o przeszukiwaniu kazdej kombinacji na całej
tablicy kliknięć sugeruje, że nawet nie przeczytałeś dokładnie:/


pzdr
bartekltg