以大O爲反向矢量的時間複雜度

Question

template <typename T> 
void reverseVector(vector<T> &vec, int start, int end) { 
    if(start < end) { 
     char temp = vec[start]; 
     vec[start] = vec[end]; 
     vec[end] = temp; 
     reverseVector(vec, start + 1, end – 1); } 
    } 
} 

假設N = vec.size（）這個方法的時間複雜度是多少？

假設我是正確的，獲取和設置矢量的時​​間爲O（1）。因此，if語句中的前3行都是O（1）。然後，該方法遞歸地調用它自己，並且每次函數變小，迭代n（n-1）（n-2）...次。所以我的答案是O（n！）這種方法。我對麼？

編輯：類似的語法，但鏈表

template <typename T> 
void reverseLinkedList(list<T> &lst, int start, int end) { 
    if(start < end) { 
    char temp = lst[start]; 
    lst[start] = lst[end]; 
    lst[end] = temp; 
    reverseLinkedList(lst, start + 1, end – 1); 
    } 
} 

Answer 1

也就是說O(n)。

你交換元素n/2時間：（0與N-1），（1 N-2），...（N/2 - 1與N/2 + 1）