论坛 › 数据结构与算法 › 函数复杂度问题求解？

BigSpoon 发表于 2016-10-24 19:00:13

函数复杂度问题求解？

本帖最后由 BigSpoon 于 2016-10-24 19:06 编辑

removeRange函数用于删除指定范围内的所有元素即[start,end),求出该函数的复杂度？
template<class T>
void arrayListWithRemoveRange<T>::removeRange(int start, int end)
{
      //                listSize为整个用数组描述的线性表的长度


   if (start < 0 || end > listSize)   //-------------theta(1)
        //illegalIndex()返回一个错误算法复杂度视为theta（1）                           
      throw illegalIndex();                  //-------------omega(0)   O(1)

   if (start >= end)                        //--------------theta(1)
      // nothing to remove
      return;                                //--------------omega(0)   O(1)

   // 将一个元素的copy视为theta(1);
   copy(element + end, element + listSize,
                        element + start); //-----theta(listSize-end)

   // destroy uneeded elements
   int newSize = listSize - end + start;//-----theta(1)
   for (int i = newSize; i < listSize; i++)//theta(max(listSize-newSzie+1,1))
      element.~T();         //---theta(max(listSize-newSize,1))
   listSize = newSize;                      //--------theta(1)
}
该方法的复杂度为 theta(max(listSize-end,end-start))?

暴力书生 发表于 2016-10-26 19:50:18

{:10_249:}

暴力书生 发表于 2016-10-26 20:04:53

加油

BigSpoon 发表于 2016-10-29 10:37:36

恩

查看完整版本: 函数复杂度问题求解？