이 코드의 복잡성을 분석하는 방법은 무엇입니까?

Question

codeforces에서 problem을 푸는 중입니다. editorial에 따르면 다음 코드의 복잡성은 O (n)이어야합니다. 여기

for(int i = n - 1; i >= 0; --i) { 
    r[i] = i + 1; 
    while (r[i] < n && height[i] > height[r[i]]) 
     r[i] = r[r[i]]; 
    if (r[i] < n && height[i] == height[r[i]]) 
     r[i] = r[r[i]]; 
} 

, height[i]i 번째는 언덕의 높이와 r[i]height[i]는보다 높은 제 오른쪽 언덕의 위치이며, height[0] 높이 어레이의 다른 값들 중 항상 가장 크다.

내 질문은 O (n) 인 코드의 복잡성을 어떻게 보장 할 수 있습니까? while while while while while?

내부 while 루프에서 코드는 >height[r[i]]까지 r[i] 값을 업데이트합니다. 업데이트 수는 높이 배열에 따라 다릅니다. 예를 들어, 높이가 감소하지 않는 순서로 정렬 된 높이 배열의 업데이트 횟수는 증가하지 않는 순서로 정렬 된 높이 배열의 업데이트 횟수와 다릅니다. (두 경우 모두이 문제에서 height[0]이 항상 최대이기 때문에 height[0]을 제외한 배열을 정렬합니다).

그리고이 같은 입력 데이터에 따라 달라지는 알고리즘을 분석 할 수있는 방법이 있습니까? 상각 한 분석은 응답의 한개 일 것인가?

추신. 내 질문을 더 명확히하고 싶습니다, 우리는 루프에 배열 r []을 설정해야합니다. 그리고 이것에 대해서? height = {5,4,1,2,3} 및 i=1 인 경우 (2가 첫 번째 값보다 크고 3이 두 번째보다 큰 첫 번째 값이기 때문에 r[2]=3, r[3]=4) 4를 1과 비교해야하며 4> 1이므로 4와 2 (= height[r[2]]), 3과 4 (= height[r[3]])를 비교하려고 계속 노력하십시오. 이 경우 r [1]을 설정하기 위해 4 번 비교해야합니다. 비교 수는 height = {5,1,2,3,4} 일 때와 다릅니다. 코드의 복잡성을 O (n)으로 보장 할 수 있습니까? 내가 뭔가를 놓친다면 알려주세요. 고맙습니다.

Answer 1

간단한 알고리즘으로 언급 한 알고리즘을 시도했지만 아무 것도 변경되지 않은 것 같습니다. 뭔가 놓쳤습니까?

예 :

n = 5 
height = { 2, 4, 6, 8, 10 } 
r = { 1, 2, 3, 4, 5 } 

---- i:4 ---- 

r[4] < 5 ? 

---- i:3 ---- 

8 > 10 ? 
8 = 10 ? 

---- i:2 ---- 

6 > 8 ? 
6 = 8 ? 

---- i:1 ---- 

4 > 6 ? 
4 = 6 ? 

---- i:0 ---- 

2 > 4 ? 
2 = 4 ? 

------------- 

height = { 2, 4, 6, 8, 10 } 
r = { 1, 2, 3, 4, 5 } 

Answer 2

귀하 너 한테 (내가 당신의 문제를 해결할지 모르는) 내부 루프가 있음에도 불구하고, 실제로 O (n)이 있지만 대부분의 경우에 주어진 조건 때문에 내부 루프가 실행되지 않습니다. 따라서 최악의 경우에는 2n 시간처럼 실행됩니다. O (n)입니다.

당신은이 내부 루프가 실행 된 것 시간의 수를 반환합니다 같은 방법으로 이러한 가정을 테스트 할 수 있습니다

:이

int arr[] = {1, 2, 3, 4, 5}; 
    do { 
     int count = yourMethod(arr, 5); 
    }while(next_permutation(arr, arr+5)); 

당신은 최악의 경우를 확인할 수있을 것입니다, 평균 경우 등 .