時間和空間，如果

Question

我該如何計算程序（僞代碼）的時間和空間複雜度如下的複雜性（areAllArrayElementsZero（）！）：

function(){ 
    if(!areAllArrayElementsZero()){ 
    if(hasAnyOdd()){ 
     decreaseOneFromFirstOddElementInArray() 
    } else { 
     divideAllArrayElementByTwo() 
    } 
    } 
} 

這裏areAllArrayElementsZero()，hasAnyOdd()，divideAllArrayElementByTwo()具有複雜性上）。任何線索都會有幫助。其實我正在設計這個problem的解決方案。

這裏是Java等效上述僞代碼的，我設計：

package competitive; 

/* 
* Problem: http://www.geeksforgeeks.org/count-minimum-steps-get-given-desired-array/ 
*/ 
class formarray{ 
    private static int[] elem; 

    private static boolean areAllZeros(){ 
     for(int i=0; i<elem.length;i++){ 
      if(elem[i]>0){ 
       return false; 
      } 
     } 
     return true; 
    } 

    private static boolean hasAnyOdd(){ 
     for(int i=0; i<elem.length;i++){ 
      if(elem[i]%2 != 0){ 
       // odd element discovered 
       return true; 
      } 
     } 
     return false; 
    } 

    private static boolean decreaseFirstOddByOne(){ 
     for(int i=0; i<elem.length;i++){ 
      if(elem[i]%2 != 0) { 
       // odd element discovered 
       elem[i]-=1; 
       // return true if one is decreased from first odd element 
       return true; 
      } 
     } 
     return false; 
    } 

    private static void DivideArrayElementsByTwo(){ 
     for(int i=0; i<elem.length;i++){ 
      // we are not checking element to be even as it has already been checked 
      elem[i] = elem[i]/2; 
     } 
    } 

    public static void main(String args[]){ 
     elem = new int[args.length]; 

     // assign values 
     for(int i=0;i<args.length;i++){ 
      elem[i] = Integer.parseInt(args[i]); 
     } 

     int steps=0; 
     while(!areAllZeros()){ 
      if(hasAnyOdd()){ 
       // the array has odd members 
       if(decreaseFirstOddByOne()){ 
        steps++; 
       } 
      } else { 
       DivideArrayElementsByTwo(); 
       steps++; 
      } 
     } 

     System.out.println("Total steps required: "+steps); 

    } 
} 

Answer 1

有執行的正好是4條路徑;總結每個成本，佔據最大的。

或者意識到沒有循環，每條路徑都有有限數量的O（n）元素，使得整個事物O（n）。