-
Data: 2013-05-12 19:24:10
Temat: Re: Zabawy w algorytmikę.
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 12.05.13 19:48 A.L.
- 12.05.13 20:02 bartekltg
- 12.05.13 21:21 Vax
- 12.05.13 22:49 bartekltg
- 12.05.13 22:51 bartekltg
- 12.05.13 23:01 Vax
- 13.05.13 00:09 bartekltg
- 13.05.13 00:12 bartekltg
- 13.05.13 01:13 A.L.
- 13.05.13 02:19 bartekltg
- 13.05.13 02:20 bartekltg
- 13.05.13 02:49 A.L.
- 13.05.13 10:14 R.e.m.e.K
- 13.05.13 10:58 M.M.
- 13.05.13 11:54 Miroslaw Kwasniak
Najnowsze wątki z tej grupy
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
- C++. Podróż Po Języku - komentarz
Najnowsze wątki
- 2025-07-03 Trybik
- 2025-07-04 Renault Symbioz
- 2025-07-04 Architektura IIIRP: Wyjątkowa, a prymitywniejsza niż stodoła pod zaborami
- 2025-07-04 Warszawa => International Freight Forwarder <=
- 2025-07-04 Wrocław => SAP ABAP Developer <=
- 2025-07-04 Warszawa => Mid/Senior IT Recruiter <=
- 2025-07-04 Białystok => Kotlin Developer <=
- 2025-07-04 Bieruń => Spedytor Międzynarodowy (handel ładunkami/prowadzenie flo
- 2025-07-04 Warszawa => Specjalista wsparcia IT - analiza techniczna sprzętu IT <
- 2025-07-04 Zakrzewo => Konsultant SAP HCM <=
- 2025-07-04 Łódź => Programista Mainframe (z/OS, Assembler) <=
- 2025-07-04 Szczecin => Key Account Manager IT <=
- 2025-07-04 Warszawa => Technik IT - Konfiguracja i Wsparcie Sprzętowe <=
- 2025-07-04 Warszawa => Technique IT - Hardware Configuration and Support <=
- 2025-07-04 Warszawa => Specjalista ds. Sprzętu IT i Wsparcia Technicznego <=