Estou com uma dúvida quanto a análise de complexidade desse código em Java:
public static int cont;
public static int recursive(int base,int numb,ArrayList<Integer> lista){
if(lista.size()>base) return 0;
if(numb<0 || numb>base-1) return 0;
ArrayList<Integer> newArray=new ArrayList<Integer>(lista.size()+1);
for(int i=0;i<lista.size();i++)
newArray.add(lista.get(i));
newArray.add(numb);
cont++;
recursive(base,numb-2,newArray);
recursive(base,numb-1,newArray);
recursive(base,numb+1,newArray);
recursive(base,numb+2,newArray);
return cont;
}
public static void main(String[] args){
int base=11;
ArrayList<Integer> test=new ArrayList<Integer>(base);
for(int i=1;i<11;i++){
recursive(base,i,test);
}
System.out.println("Números validos com digitos repetidos:"+cont);
}
Não consigo fazer a análise desse algoritmo. Eu devo criar uma variável instrução
por exemplo, e dar um instrução++
em cada if
, atribuição, entrada no for
ou já que esse algoritmo tem tempo de execução constante dizer que ele é O(1)? Ou ainda, só contar quantas vezes a recursão é chamada?