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?
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 ano. Ale převod z 2D na 1D a pak prohledání 1D by zabralo ještě víc času.
No tohle samozřejmě nedělat.
Pak asi nezbude, než procházet každý řádek zvlášť.
Ještě mě napadá otázka, je lepší procházet po řádcích, sloupcích? Nebo je to jedno? Mám pocit, že jsem někde slyšel že řádky jsou lepší, je to pravda?
Vždycky procházíš nejdříve první pole, kde získáš ukazatele na další pole. Jestli to první pole nazveš sloupce, pak jsou další pole řádky. Nebo to také může být naopak. Je to jedno.
ok, díky
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)