java - Big O complexity decision -
i got big doubt regarding complexity analysis of code. need study complexity of "encontrarcaminos()" method , i'm torn between being o(n*m) since gets iterate n times (thru array.aslist (caminos) finding simultaneous ways thru maze -in can never go in direction point passed-) , iterating again 6 times each n due directions go thru.
n number of iterations , increases.
m number of directions checks, clearer.
or, it's o(n) because 6 m times (directions) constant , therefore can ignore em?.
also, if had count cycles/instructions, should put "cycles++;" counter method in particular? it's kinda related previous question, determining complexity that.
here piece of code in question:
public void encontrarcaminos() { boolean complete=false; int i=0; while(!complete) { (dir3d d: dir3d.values()) { camino caux = this.camino(i).copiar(); caux.agregardireccion(d); posicion paux = caux.posicionfinal(); if(chequearlimite(paux) && this.get(paux)) { this.agregarcamino(caux); this.set(paux, false); } } i++; if( this.cantcaminos()==(this.xmap*this.ymap*this.zmap)) complete=true; } system.out.println(caminos); } //auxiliary things below, of pretty straigthforward, still. ############################################################################### public boolean chequearlimite(posicion p) { return 0<=p.getx() && p.getx()<this.xmap && 0<=p.gety() && p.gety()<this.ymap && 0<=p.getz() && p.getz()<this.zmap; } ############################################################################## public int cantcaminos() { return caminos.size(); } ############################################################################### public void agregardireccion(dir3d dir) { direcciones.add(dir); if (dir == dir3d.atras) posicionfinal.sety(posicionfinal.gety()-1); if (dir == dir3d.derecha) posicionfinal.setx(posicionfinal.getx()+1); if (dir == dir3d.arriba) posicionfinal.setz(posicionfinal.getz()+1); if (dir == dir3d.adelante) posicionfinal.sety(posicionfinal.gety()+1); if (dir == dir3d.izquierda) posicionfinal.setx(posicionfinal.getx()-1); if (dir == dir3d.abajo) posicionfinal.setz(posicionfinal.getz()-1); } ######################################################################################## public camino copiar() { camino aux = new camino(posicion.copiar(posicioninicial)); (int i= 0;i<direcciones.size();i++) { aux.agregardireccion(direcciones.get(i)); } return aux; } ######################################################################################## public camino camino(integer indice) { return caminos.get(indice); } any insight or appreciated.
let's refer this.xmap*this.ymap*this.zmap matrix-size.
it looks o((matrix-size)^2) me. since direcciones being appended constant number of times per run of outer loop, calls copiar o(matrix-size) in time. each loop iteration adds @ size of dir3d items (also constant) caminos. continues until total of matrix-size items have been added.
one thing didnt check if possible add more matrix-size -- in case never terminate.
Comments
Post a Comment