我們如何計算以下程序的時間複雜度：

-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

我們如何計算以下程序的時間複雜度：

回答

相關問題