Как определить, что является элементарной операцией в алгоритме?

Question

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

И как таковой, в этом алгоритме:

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (true) {
            int N = in.nextInt();
            if (N == 0)
                break;

            long cost = 0;
            int[] houses = new int[N];
            for (int i = 0; i < N; ++i)
                houses[i] = in.nextInt();

            for (int i = 0; i < N - 1; ++i) {
                cost += Math.abs(houses[i]);
                houses[i + 1] += houses[i];
            }
            System.out.println(cost);
        }
    }
}

Я сказал, что элементарной операцией была операция присваивания houses[i] = in.nextInt(); внутри первого for, потому что он выполняется N раз, а второй for - N-1 раз.

Мой учитель говорит, что это неверно и что элементарная операция в этом алгоритме - это операция внутри второй функции.

Вероятно, есть исключения, когда элементарная операция не является операцией, расположенной внутри самого внутреннего цикла, или она ошибочна?

Answer 1

Элементарная операция - это операция, время выполнения которой ограничено константой для конкретной машины и языка программирования. Это означает, что если мы запускаем элементарную операцию, написанную на определенном языке, на определенной машине, для ее выполнения всегда требуется одно и то же время. Например, присваивание, сложение, умножение и т. Д. В вашем случае операция in.nextInt(); под первым циклом на самом деле находится событие ввода с клавиатуры, вид операций ввода-вывода, которые в основном зависят от пользователей. Так что это не элементарная операция.

Answer 2

Для этой программы второй цикл for не находится внутри первого цикла for.

Эта программа принимает N чисел в качестве входных данных для массива домов, и фактический алгоритм находится только во втором цикле for, где он хранит текущий счет стоимости первых i элементов массива в i-м индексе.

Ваш учитель прав.