时间和空间，如果

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）。