가장 빠른 방법으로 특정 간격의 요소를 1 씩 증가시킵니다.

Question

배열로 표시된 요소의 목록이 있습니다. 주어진 간격 (l, r)에 대해 '1'이 이들 요소에 추가되어야합니다.

for(i=l;i<=r;i++) 
    A[i]++; 

잘 작동합니다. 그러나 많은 수의 계승을 찾기위한 프로그램을 만들고 있습니다. 계승 알고리즘은 더 높은 시간 복잡성을 필요로하므로 앞서 계승을 수행해야하는 위 단계의 시간 복잡성을 줄여야합니다.

Answer 1

한 번에 2 개 요소의 Array 값을 증가시켜 시간 복잡성을 줄일 수 있습니다.

나는 아래의 코드가 시간 복잡성을 O (n)에서 O (n/2)로 줄일 것이라고 생각한다.

for(i=l; i<=r; i++) 
{ 
if(i!=r) 
A[r]++; 
A[i]++; 
r--; 
} 

설명 :

단위 시작 인덱스와 인덱스 종료 모두에서 배열 요소 값.

두 색인이 모두 같을 경우 색인은 중간 요소를 가리 킵니다. 그래서 하나의 요소 (중간 요소) 만 증가시킵니다.