Как анализировать сложность этого кода?

Question

Я решаю problem от codeforces. Согласно 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?

В то время как внутренний цикл, код обновляет r[i] значения, пока height[i]>height[r[i]]. а количество обновлений зависит от массива height. Например, количество обновлений массива высоты, отсортированных по неубывающему порядку, будет отличаться от числа массива высоты, отсортированного по неубывающему порядку. (в обоих случаях мы будем сортировать массив, кроме height[0], потому что height[0] всегда должен быть максимальным в этой задаче).

И есть ли какой-либо метод для анализа алгоритма, который меняется на входные данные следующим образом? Амортизированный анализ будет одним из ответов?

PS. Я хотел бы уточнить мой вопрос: «Мы должны установить массив r [] в цикле. А как насчет этого? если массив height = {5,4,1,2,3} и i=1, (r[2]=3, r[3]=4, потому что 2 - первое значение, которое больше 1, а 3 - первое значение, большее 2), мы должны сравнивать 4 с 1, а поскольку 4> 1, мы продолжайте пытаться сравнивать 4 и 2 (= height[r[2]]), 4 с 3 (= height[r[3]]). В этом случае мы должны сравнить 4 раза, чтобы установить r [1]. Количество сравнения отличается от 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 (п), даже если есть внутренняя петля, но в большинстве случаев внутренний цикл не будет выполняться из-за заданных условий. Поэтому в худшем случае он будет работать как 2n времени, что и O (n).

Вы можете проверить это предположение с помощью метода, как это, где будет возвращать количество времени, это внутренний цикл были выполнены:

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

При этом вы сможете проверить худший случай, средний случай, и т.д. .