鱼C论坛

 找回密码
 立即注册
查看: 3363|回复: 3

函数复杂度问题求解?

[复制链接]
发表于 2016-10-24 19:00:13 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 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[i].~T();         //---theta(max(listSize-newSize,1))
   listSize = newSize;                      //--------theta(1)
}
该方法的复杂度为 theta(max(listSize-end,end-start))?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-10-26 19:50:18 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-10-26 20:04:53 | 显示全部楼层
加油
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-10-29 10:37:36 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-1-13 12:27

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表