我们如何计算以下程序的时间复杂度：

-1

我觉得难以计算以下程序的时间复杂度，请给出一些建议？我们如何计算以下程序的时间复杂度：

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; 
    } 
}

我写了这个代码返回两个数字，使得他们增加了特定目标的指数。每个输入只能有一个解决方案。现在我必须计算复杂性来检查并提交代码

来源

2017-09-15 shivoham

您是否研究过如何计算算法的复杂性？可能是一个开始的好地方。您的帖子显示没有事先研究，目前看起来像是一个请求，而不是一个实际的问题。查看[帮助中心]（https://stackoverflow.com/help）获取关于如何发布问题的建议。 –

检查此：https://stackoverflow.com/questions/16232629/what-is-time-complexity-and-how-to-find-it – 2017-09-15 06:14:02

我试图调查它。我能够计算何时涉及单循环或双循环或二进制，但是当涉及到散列或递归或2-3个结构时，我似乎总是无法达到正确的复杂度。这是一个需要检查的问题这个代码的复杂性是什么，所以我可以优化它 – shivoham

您确定这是否适合？即使这样做，在最坏的情况下，这最终可能会呈指数级的时间复杂度。尝试使用蛮力解决方案，通过循环遍历每个元素x并查找是否有另一个值等于target - x（将为O(n^2)），您可以考虑使用线性扫描和hashmaps的更优化解决方案。

来源

2017-09-15 06:14:12

其实它有O（N^2）的复杂性（但有时它永远不会完成）。仔细看看'twoSum'递归调用是否在循环之外。 – talex

我们如何计算以下程序的时间复杂度：

回答

相关问题