函数复杂度问题求解？

BigSpoon

removeRange函数用于删除指定范围内的所有元素即[start,end),求出该函数的复杂度？

1. template<class T>
   
2. void arrayListWithRemoveRange<T>::removeRange(int start, int end)
   
3. {
   
4.       //                listSize为整个用数组描述的线性表的长度
   
5. 
   
6. 
   
7.    if (start < 0 || end > listSize)   //-------------theta(1)
   
8.         //illegalIndex()返回一个错误算法复杂度视为theta（1）                           
   
9.       throw illegalIndex();                    //-------------omega(0)   O(1)
   
10. 
    
11.    if (start >= end)                        //--------------theta(1)
    
12.       // nothing to remove
    
13.       return;                                //--------------omega(0)   O(1)
    
14. 
    
15.    // 将一个元素的copy视为theta(1);
    
16.    copy(element + end, element + listSize,
    
17.                         element + start); //-----theta(listSize-end)
    
18. 
    
19.    // destroy uneeded elements
    
20.    int newSize = listSize - end + start;//-----theta(1)
    
21.    for (int i = newSize; i < listSize; i++)//theta(max(listSize-newSzie+1,1))
    
22.       element[i].~T();         //---theta(max(listSize-newSize,1))
    
23.    listSize = newSize;                      //--------theta(1)
    
24. }

复制代码

该方法的复杂度为 theta(max(listSize-end,end-start))?

暴力书生

暴力书生

加油

BigSpoon

恩