Comment pouvons-nous calculer la complexité du temps du programme ci-dessous:

Question

Je trouve difficile de calculer la complexité du temps du programme ci-dessous. S'il vous plaît donner quelques suggestions?

class Solution { 
    int i=0,j=1,k,m; 
    public int[] twoSum(int[] nums, int target) { 

     int sum; 
     boolean flag=false; 
     int arr[] = new int[2]; 
     for(k=j;k<nums.length;k++){ 
      sum=nums[i]+nums[k]; 

      if(sum==target){ 
       flag=true; 
       m=k; 
       break; 
       } 
     } 
     if(flag==false){ 
      i++; 
      j++;     
      twoSum(nums,target); 
     } 

     arr[0]=i; 
     arr[1]=m; 
     return arr; 
    } 
} 

J'ai écrit ce code pour retourner les indices des deux nombres tels qu'ils ajoutent à une cible spécifique. chaque entrée aurait exactement une solution. maintenant je dois calculer les complexités pour vérifier et soumettre le code

Answer 1

Etes-vous sûr que cela fonctionne? Même si c'est le cas, cela peut finir par avoir une complexité exponentielle dans le pire des cas. Essayez avec une solution brute force où vous bouclez chaque élément x et trouvez s'il y a une autre valeur qui équivaut à target - x, qui sera O(n^2), vous pouvez penser à une solution plus optimale qui utilise des balayages linéaires et des hashmaps alors.