Suma elementów macierzy kwadratowej - jest jakaś własność ?

[pi0tras]

Cześć, muszę napisać "efektywny" program który sprawdza czy suma elementów macierzy jest parzysta czy nie, jest to macierz kwadratowa \(\displaystyle{ n \ \times \ n , \ \ n \in \mathbb{N}}\), której elementami mogą być tylko \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\), gdybym miał pisać taki program "na odwal" to musiał bym sprawdzić wszystkie elementy macierzy: \(\displaystyle{ n^{2}}\) dostępów do macierzy bym potrzebował,a skoro ma być "efektywny" to pewnei trzeba zrobić program o mniejszej złożonosć czasowej, jest jakaś własność macierzy określajaca sume jej elementów przy warunkach które podałem ? Dzięki za pomoc z góry ; )

[TPD]

Wydaje mi się ze nie. Mozna sie zastanowić nad przypadkiem macierzy symetrycznej, ale w dowolnej takiej zależności nie powinno być.

[pi0tras]

Szkoda, więc ciekawe co to znaczy, że ma być "Efektywna" skoro i tak wszystkie miejsca musze przejrzeć

[a4karo]

A jak chciałbyś się dowiedzieć co jest na \(\displaystyle{ i,j}\)-tym miejscu nie sprawdzajac go?

[pi0tras]

Właściwie to nie muszę się tego dowiadywać, muszę tylko wiedzieć czy suma tych wszystkich elementów (zer lub jedynek) jest parzysta czy nie, naiwny algorytm wykona to przy \(\displaystyle{ n^{2}}\) dostępach do macierzy wejściowej, w zadaniu jest mowa o algorytmie efektywnym więc nie wiem co mam przez to rozumieć ?

[norwimaj]

Nie da się wykonać tego zadania nie oglądając wszystkich elementów macierzy. Jeśli jest choć jeden nieobejrzany element, to zmieniając jego wartość zmienimy parzystość sumy i algorytm nie ma szansy się o tym dowiedzieć. Dla tego zadania naiwne rozwiązanie jest najlepsze. Może to miało być zadanie ze współbieżności? Jeśli masz \(\displaystyle{ n}\) procesorów, to wtedy można trochę przyspieszyć.