역방향 벡터에 대한 큰 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 문의 처음 세 줄은 모두 모두 O (1) 개입니다. 그런 다음이 메소드는 반복적으로 자신을 호출하고 함수가 작아 질 때마다 n (n-1) (n-2) ... 번 반복합니다. 그래서 내 대답은 O (n!)이 방법입니다. 나 맞아?

편집 : 유사한 구문하지만, 연결리스트 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

와.

당신은 요소를 n/2 번 교환 : (0 N-1), (1, N-2), (N/2-1와 N/2 + 1)