Эффективный один алгоритм из этих двух алгоритмов

Question

Оба эти алгоритма дают одинаковый вывод, но первый занимает почти двукратное время (> .67) по сравнению со вторым (.36).Как это возможно?Можете ли вы сказать мне сложность времени обоих алгоритмов?Если они одинаковы, почему время отличается?

1-й алгоритм:

 for (int i =0 ;i<n;i++){
        cin>>p[i];
        if(i>0){
            if(p[i-1]>p[i]){
                cout<<p[i]<<" ";
            }
            else{
                cout<<"-1"<<" ";
            }
        }
    }

2-й алгоритм:

for (int i =0 ;i<n;i++){
        cin>>p[i];

    }
    for (int i =0 ; i<n-1;i++){
       if(p[i]>p[i+1]){
                cout<<p[i]<<" ";
            }
            else{
                cout<<"-1"<<" ";
            } 
    }

Answer 1

Сложность времени в современном процессоре может быть практически бесполезной статистикой производительности.

В этом случае у нас есть один алгоритм, который идет от 0 до n-1 - O (N) - и второй, который идет от 0 до n-1 дважды - константа выпадает, поэтому она все еще O (N) , Первый алгоритм имеет дополнительный оператор if, который будет ложным ровно один раз, и приличный компилятор уничтожит его. Мы получаем одинаковое количество входных данных, одинаковое количество выходных данных, одинаковое количество обращений к массиву (своего рода) и одинаковое количество if (a>b).

То, что у второго есть, чего у первого нет, так это детерминизм. Один цикл определяет все для второго. Все входные данные считываются в первом цикле. Это означает, что ЦП может точно видеть, что произойдет раньше времени, потому что он имеет все числа и, таким образом, точно знает, как пойдет каждая ветвь if и может предсказать со 100% точностью, загрузить кеши, и заполнить конвейеры, чтобы все было готово заранее, не пропуская ни секунды.

Алгоритм 1 не может этого сделать, потому что следующий вход не известен до следующей итерации цикла. Если шаблон ввода не является предсказуемым, он будет угадывать, в каком направлении if(p[i-1]>p[i]) будет часто работать неправильно.

Дополнительное чтение: Почему быстрее обрабатывать отсортированный массив, чем несортированный массив?