如何定义算法中的基本操作？

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);
        }
    }
}

我说过基本操作是第一个for中的赋值操作houses[i] = in.nextInt();，因为它运行N次，而第二个for运行N-1次。

我的老师说这是不正确的，这个算法中的初等操作是第二个for中的操作。

有没有例外，基本操作不是位于最内层循环中的操作，或者她是错的？

Answer 1

对于这个程序，第二个For循环不在第一个for循环内。

此程序将N个数字作为house数组的输入，实际算法仅在第二个for循环中，其中它将数组的前i项的成本的运行计数保存在第i个索引中。

你的老师是对的。

Answer 2

基本操作是指其执行时间受特定机器和编程语言的常量限制的操作。这意味着如果我们在一台特定的机器上运行一个用特定语言编写的基本操作，它总是花费相同的时间来执行。例如赋值、加法、乘法等。在你的例子中，第一个循环下的操作in.nextInt()；实际上是一个键盘输入事件，一种IO操作，这主要取决于用户。所以这不是一个基本的操作。