我想计算下的复杂性 指数递归函数。

I am trying to calculate the complexity of the following exponential recursive function.

在isMember（）和isNotComputed（）函数数量减少 递归调用。

The isMember() and isNotComputed() functions reduce the number of recursive calls.

这code的输出是一组A的[]，B []这是印在 递归函数调用的初始部分。

The output of this code is a set of A[], B[] which are printed at the initial part of recursive function call.

将为AP preciate开发这个递归关系的任何输入 问题，这将导致该方案的分析。

Would appreciate any inputs on developing a recursive relationship for this problem which would lead to the analysis of this program.

如果没有功能isMember（），isNotComputed（）这个code具有复杂性为O（2 ^ N）。根据经验（与上面两个功能）此code具有复杂性为O（| N ^ 2 ||大号|）。其中L是制成递归调用的次数，即结果产生的。

Without the functions isMember(), isNotComputed() this code has the complexity of O(2^N). Empirically (with the above two functions) this code has a complexity of O(|N^2||L|). Where L is the number of recursive calls made, i.e. results generated.

我试图计算出这个code尽可能准确的复杂性，这样我可以这样做的效率与一组其他算法，它在本质上类似的比较。

I am trying to calculate the complexity of this code as accurate as possible, so that I can compare the efficiency of this with a set of other algorithms which are similar in nature.

void RecuriveCall(int A[], int ASize, short int B[], int BSize, 
              int y, short int level) { 
    int C[OBJECTSIZE]; 
    short int D[ATTRIBUTESIZE]; 
    int CSize, DSize; 
    PrintResult( A,ASize, B, BSize);                                                                         
    for (int j=y; j<n; j++) {                                                  
        if (! isMember(j, B, BSize)) {                                      
            function1(C,CSize,A,ASize,j);                             
            function2(D,DSize,C, CSize);                                 
            if (isNotComputed(B, BSize, D, DSize, j)) {                                                                                     
                RecursiveCall(C, CSize,D, DSize, j+1, level+1); 
            }      

        } 
    } 

}    

// Complexity - O(log N) - Binary Search
bool isMember(int j,short int B[], int BSize) { 
    int first, mid, last; 
    first = 0; 
    last = BSize-1; 

    if (B[first] == j || B[last] == j) { 
        return true; 
    } 

    mid = (first+last)/2; 
    while (first <= last) { 
        if (j == B[mid]) { 
            return true; 
        } 
        else if (j < B[mid])  
            last = mid-1; 
        else
            first = mid+1; 
        mid = (first+last)/2; 
    } 
    return false; 
}
// complexity - O(N)
bool isNotComputed(short int B[], int BSize, short int D[], int DSize,int j) { 
    if (j==0) { 
        return true; 
    } 

    int r = 0; 
    while (r<BSize && B[r]<j && r<DSize && D[r]<j) { 
        if (B[r] != D[r]) { 
            return false; 
        } 
        r=r+1; 
    } 
    // Now we can check if either B[] or D[] has extra elements which are < j 
    if (r<BSize && r < DSize && B[r]>=j && D[r] >=j) {// we know it is okay 
        return true; 
    } 
    if (r==BSize && r==DSize) {  
        return true; 
    } 
    if (r==BSize && r<DSize && D[r] >=j) {  
        return true; 
    } 
    if (r==DSize && r<BSize && B[r] >=j) { 
        return true; 
    } 
    return false; 
} 


// Complexity - O(N)
void function1(int C[],int &CSize,int A[] ,int ASize,int j) { 
    int tsize = 0; 
    for (int r=0;r<ASize;r++) 
        if (I[A[r]][j]==1) 
            C[tsize++] = A[r]; 
    CSize = tsize; 
} 

// Complexity - O(|N||G|) - G - number of objects
void function2(short int B[], int &BSize,int A[], int ASize) { 
   int i,j; 
   int c=0; 
    // Iterate through all attributes 
   for (j = 0; j < MAXATTRIBUTES; ++j) { 
      // Iterate through all objects 
      for (i = 0; i < ASize; ++i)  
         if (!I[A[i]][j]) 
            break; 
      if (i == ASize)  
         B[c++] = j; 
   } 
   BSize = c; 
}

void main() {
   n = MAXATTRIBUTES;
   for (int r=0; r<MAXOBJECTS; r++) 
       A[r] = r; 
   ASize = MAXOBJECTS; 
   function2(B, BSize, A, ASize); 

   RecursiveCall(A, ASize,B, BSize, 0, 0); 
}

由psented答案$ P $穆罕​​默德ennahdi EL idrissi地址如何递归关系可以发展。

The answer presented by "mohamed ennahdi el idrissi" addresses how a recursive relationship can be developed.

你怎么把功能isMember（）和isNotComputed（）函数到这一点。从本质上说，这些减少的显著做递归调用的次数。是否有引入一个概率函数来重新present他们的一种方式？即P（F（N））xRecCall第（n-1）。我已经看到了一些算法的复杂性被计算如为O（N ^ 2.48）。你怎么来了这样的价值观？

How do you incorporate the functions isMember() and isNotComputed() functions into this. In essence these reduce the number of recursive calls made significantly. Is there a way of introducing a probabilistic function to represent them? i.e P(f(n))xRecCall(n-1). I have seen the complexity of some algorithms been computed e.g. as O(N^2.48). How do you come with such values?

推荐答案

我试图适应以下递推关系到code，请参见下面的步骤：

I have tried to adapt the following recurrence relation to your code, see the steps below:

其中， N = MAXATTRIBUTES （不变），而 M = A大小。