Comment trouver la complexité temporelle des algorithmes de backtracking dfs +?

Question

Je suis en train de résoudre ce problème sur leetcode https://leetcode.com/problems/factor-combinations/description/

Les nombres peuvent être considérés comme produit de ses facteurs. Par exemple

8 = 2 x 2 x 2; = 2 x 4.

Ecrivez une fonction qui prend un entier n et renvoie toutes les combinaisons possibles de ses facteurs.

alors que je suis capable d'écrire le code en utilisant l'approche dfs, j'ai du mal à gérer la complexité de son pire temps en termes d'entrée. quelqu'un peut-il aider s'il vous plait?

public List<List<Integer>> getFactors(int n) { 
     List<List<Integer>> result = new ArrayList<List<Integer>>(); 
     List<Integer> current = new ArrayList<Integer>(); 
     getFactorsHelper(n,2,current,result); 
     return result; 
    } 


    public void getFactorsHelper(int n,int start,List<Integer> current, List<List<Integer>> result){ 
     if(n<=1 && current.size()>1){ 
      result.add(new ArrayList<>(current)); 
      return; 

     } 
     for(int i=start;i<=n;i++){ 

      if(n%i==0) { 
       current.add(i); 
       getFactorsHelper(n/i,i,current,result); 
       current.remove(current.size()-1); 
      }    

     } 

    } 

Answer 1

Je calcule la complexité de votre code comme ceci:

Considérons la runtime de getFactorsHelper(n,2) est fonction T(n).

Dans la partie suivante, vous avez une boucle avec l'index i.

for(int i=start;i<=n;i++){  
      if(n%i==0) { 
       current.add(i); 
       getFactorsHelper(n/i,i,current,result); 
       current.remove(current.size()-1); 
      }    
     } 

Le n est divisé par i à chaque itération. Nous avons donc:

(première itération)

getFactorsHelper(n/2,2,current,result) = T(n/2) 

(deuxième itération)

getFactorsHelper(n/3,3,current,result) <= getFactorsHelper(n/3,2,current,result) = T(n/3) 

(troisième itération)

getFactorsHelper(n/4,4,current,result) <= getFactorsHelper(n/4,2,current,result) 
= T(n/4) 

...

(version finale)

getFactorsHelper(n/n,n,current,result) <= getFactorsHelper(n/n,2,current,result) = T(n/n) = T(1) 

coût total

T(n) <= T(n/2) + T(n/3) + T(n/4) + ... + T(1) 

Résolution de fonction récursive

J'espère que cela peut vous aider.

Answer 2

Impossible de publier la solution dans le commentaire. Post comme une autre réponse ici @AliSoltani https://discuss.leetcode.com/topic/30752/my-short-java-solution-which-is-easy-to-understand

public class Solution { 
public List<List<Integer>> getFactors(int n) { 
    List<List<Integer>> ret = new LinkedList<List<Integer>>(); 
    if(n <= 3) return ret; 
    List<Integer> path = new LinkedList<Integer>(); 
    getFactors(2, n, path, ret); 
    return ret; 
} 

private void getFactors(int start, int n, List<Integer> path, List<List<Integer>> ret){ 
    for(int i = start; i <= Math.sqrt(n); i++){ 
     if(n % i == 0 && n/i >= i){ // The previous factor is no bigger than the next 
      path.add(i); 
      path.add(n/i); 
      ret.add(new LinkedList<Integer>(path)); 
      path.remove(path.size() - 1); 
      getFactors(i, n/i, path, ret); 
      path.remove(path.size() - 1); 
     } 
    } 
}}