大 O 复杂性决策

Question

我对这段代码的复杂性分析产生了很大的疑问。我需要研究 "encontrarCaminos()" 方法的复杂性，我在 O(n*m) 之间左右为难，因为它要迭代 n 次（通过 array.aslist (Caminos) 找到所有同时穿过迷宫的方法 - 在这个迷宫中，你永远无法朝着你已经通过的点的方向前进 -) 并且由于你经过的所有方向，每个 n 再次重复它 6 次。

n 是 i 的迭代次数及其增量。

m是它检查的方向数，只是为了更清楚。

或者，它是 O(n)，因为 6 m 次（方向）是一个常数，因此我可以忽略 em?。

此外，如果我必须计算所有 cycles/instructions，我应该将此方法的 "cycles++;" 计数器放在哪里？这与我之前的问题有点相关，因为确定它的复杂性将对此有所帮助。

这是有问题的代码段：

http://pastebin.com/1mMGmigM

public void encontrarCaminos()
{
        boolean complete=false;
        int i=0;
        while(!complete)
        {
                for (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, some of those are pretty straigthforward, but 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));
        for (int i= 0;i<direcciones.size();i++)
        {
                aux.agregarDireccion(direcciones.get(i));
        }
        return aux;
}

########################################################################################

public Camino camino(Integer indice)
{
        return caminos.get(indice);
}

任何对此的见解或帮助将不胜感激。

Answer 1

让我们将 this.xMap*this.yMap*this.zMap 称为矩阵大小。

对我来说它看起来是 O((矩阵大小)^2)。由于 direcciones 被附加到每个运行外循环的某个常数次数，因此对 copiar 的调用在时间上为 O(matrix-size)。然后每次循环迭代最多将 Dir3D 项目的大小（也是一个常数）添加到caminos。这一直持续到总共添加了矩阵大小的项目。

我没有检查的一件事是是否可以添加超过矩阵大小的内容——在这种情况下您永远不会终止。

大 O 复杂性决策

Big O complexity decision

java

algorithm

big-o