大O的幫助，我有一個基本的想法

Question

我正在研究下面的代碼的大O時間複雜性。代碼所做的是遞歸調用，以解決在所有寶石都在單個杯子中之前執行empty操作的嘗試。

到目前爲止，我得到的是，遞歸調用從限制調用solve，直到限制現在爲1.因此，大O是（限制，限制-1，限制-2，直到限制= 1） 。

這個遞歸函數是O（n）嗎？

public void solve(Cups cups, int limit, boolean debug){ 
     String prevState = cups.toString(); 
     for(int i = 0; i < cups.size(); i++){ //for every cup 
      Cups emptyCups = cups.empty(i); //make a new instance and empty the contents of cup 
      emptyCups.stateList.addAll(cups.stateList); 
      emptyCups.stateList.add(prevState); //add previous state to stateList arraylist 
      emptyCups.moveList.addAll(cups.moveList); //add all moves to arraylist 
      emptyCups.moveList.add(i); //add i position to move list 
      if(debug = true){ 
      System.err.println(prevState + " empty-cup:"+ i + 
           ", limit:" + limit + " => " + emptyCups); 
      } 
      if(emptyCups.size() == 1){ //base case 
      StringBuilder solution = new StringBuilder("moves:" + emptyCups.moveList); 
      solution.append(" cups:"); 
      for(int j = 0; j < emptyCups.stateList.size(); j++){ 
       solution.append(emptyCups.stateList.get(j) + " "); 
      } 
      solution.append(emptyCups.toString()); 
      System.out.println(solution); 
      unsolvable = false; 
      } else if(limit > 1){ 
      solve(emptyCups, limit - 1, debug); 

Answer 1

不管你有多少杯，我都會假定尺寸是一個常量。

此代碼將是（O（n）），其中n是限制值。這是因爲每次增加1次時，此方法會運行一次額外的時間。如果限制高於低於此值，那麼在該方法內可以看到的工作量不會增加。每次調用方法都需要完成很多事情，但是由於每次都是有限數量的「內容」，因此不會影響複雜性。