Время выполнения Условный заявления с несколькими условиями

Question

Предположим, что существует массив А, содержащего п элементов, а строка кода, которая содержит Условный оператор с несколькими условиями, например:

for i = 2 to n 
    if A[i] > m and A[i] - A[1] = EVEN 
     then set m to A[i] 

ли среда выполнения для второй строки n-1, или это 2 * (n-1), так как существуют два условия для оператора if?

Answer 1

Вообще говоря, когда вы говорите о времени выполнения, вам нужна какая-то «модель затрат», чтобы говорить о том, сколько каждой операции «стоит». На самом деле довольно необычно видеть модель затрат, которая войдет в уровень детализации, в который вы входите, - обычно вы просто абстрагируете детали и говорите, что стоимость выполнения всех этих тестов - O (1) (некоторая константа, которая не зависит от размера ввода), а не рассчитывается с точностью до уровня.

Если вы собираетесь рассчитывать на точный уровень, вы также можете учитывать стоимость поиска в массиве, независимо от того, происходит ли короткое замыкание, эффект предсказания ветвления или неверное предсказание во время выполнения, и т. д., и это частично объясняет, почему так редко бывает, что люди действительно говорят о вещах на этом уровне детализации.