c++ - 推导以下代码的执行时间增长率(BigO)

Question

这段代码的执行时间增长率Big O是多少？

void doDiff(int setA[], int setB[], int sizeA, int sizeB)   {

   const int MAX = 10; 
   // validate setA and setB 
   if ((sizeA == 0) && (sizeB == 0))                    
         cout << "both sets are empty " << endl;    
   else
         cout << "symmetric difference: { " ;   

   for (int i = 0;  i <  sizeA;  i++ )            
       if (!member(setB, setA[i],sizeB))        
              cout << setA[i] << " ";           

   for (int i = 0;  i <  sizeB;i++ )            
       if (!member(setA, setB[i],sizeA))            
              cout << setB[i] << " ";                

   cout << "}" << endl;                 
}

bool member(int set[], int n, int size)
{
    for (; size > 0;  size--)               
        if (set[size-1] == n)                       
            return true;                    
  return false;         
}

当我计算这段代码的大 O 时，我得到 O(N*N*N) || O(N^3) 我不确定这段代码的确切执行时间增长率是多少。 请帮我。

提前致谢

Answer 1

用问题来填充答案似乎不合适，但由于这听起来像是家庭作业，我认为它们是实现目标的更好方法(让您弄清楚这是如何工作的):

1. member 的“big-O”是什么？这很重要，因为 doDiff 非常依赖它。
2. doDiff 调用了多少次 member？
3. 如果对member 的每次调用都花费相同的时间，则member 为O(X)，并且doDiff 调用member Y 次，doDiff 的“big-O”是什么？