poradna.net
Hledání maxima (int) v 2D poli, lze líp než o(n^2)? Ahoj,
nevíte, zda-li jde najít maximum v 2D poli intů lépe než):
for (int i = 0; i < twodArray.length; i++) {
for (int j = 0; j < twodArray[i].length; j++) {
//.......Pokud jo, tak jak?
| Předmět | Autor | Datum |
|---|---|---|
| Kdybys to 2D pole měl implementované ve skutečnosti jako 1D pole, tak vyhledáváš sekvenčně a máš slo… Niko Bellic 03.10.2015 16:51 |
Niko Bellic | |
| to sice ano, ale to tvoje N bude rovno poctu prvku, ktery je n^2, takze stejne musis projit kazdy pr… nový gilhad 05.10.2015 22:58 |
gilhad | |
| Wut?
Tohle neni slozitost n^2, ale normal n. Rychleji to udělat nejde a kdybys to převedl na 1D pol… nový MaSo 05.10.2015 23:05 |
MaSo | |
| Ten algoritmus z dotazu je O(N) poslední MM.. 05.10.2015 23:05 |
MM.. |
Zpět do poradny Odpovědět na původní otázku Nahoru
Kdybys to 2D pole měl implementované ve skutečnosti jako 1D pole, tak vyhledáváš sekvenčně a máš složitost O(N).
to sice ano, ale to tvoje N bude rovno poctu prvku, ktery je n^2, takze stejne musis projit kazdy prvek aspon jednou, pokud nemas nejake dodatecne informace (jako ze to pole je setrideno, nebo tak neco).
Jinak rychlost prochazeni 2D (n,n) a 1D (n*n) (tedy se stejnym poctem prvku) je v podstate stejna, (jako ve smyuslu poctu "velkych" operaci), ale pri prochazeni 1D nemusis delat radkove prechody a na urovni assembleru se to da napsat rychleji, ze jen inkrementujes pointer.
U 2D to jde rychleji udelat po radcich - zase misto vypoctu adres jen inkrementujes pointer, plus pripadny preskok na dalsi radek prictenim konstatnty, pokud to na sebe nenavazuje.
U porovnani a hoodne velkych poli to muze mit smysl, pokud by to porovnavani byla slozita operace (treba retezce misto bytu) a pole mala, tak se ta rezie navic v podstate ztrati.
Navic optimalizujici kompilator to muze upravit oboji na stejny tvar, v nekterych pripadech i rozvine (castecne ci zcela) vnorene smycky a vysledny kod je o dost jiny nez zdrojak (ackoli dela "to same"), takze tezko rict.
Nejjednodussi je si napsat priklad a proste to zmerit (ne stopkama, primo programem)
Obecne receno - nejde to maximum nalezt mensim poctem kroku, nez pocet prvku pole, protoze kazdy prvek musis precist a s necim porovnat, jinak by se ti mohlo stat, ze preskocis prave ten nejvetsi.
Wut?
Tohle neni slozitost n^2, ale normal n. Rychleji to udělat nejde a kdybys to převedl na 1D pole, tak budeš potřebovat pořád stejně iterací k nalezení maxima (počet prvků je stejný) + režie na flatten pole...
Ten algoritmus z dotazu je O(N)