java - 什么是一次性算法，我的算法是什么？

Question

对于我正在上的类(class)，最好使用one-pass algorithm 来解决特定任务。由于这门课不在我的专业范围内(我是建筑环境，这门课是计算机科学)，而且在类里面没有讨论，所以我不知道什么是一次性算法。谷歌搜索让我想到了这样的事情:

Each input can only be accessed once, and everything should be processed in order.

对于我下面的代码，这表明 for 循环 适合one-pass 算法，但我不确定 while循环。

您能告诉我one-pass algorithm 意味着什么吗？我的下面的代码是否符合这个描述？

public int[] computeDepth(int tree[]) {
    int[] depth = new int[tree.length];

    depth[0] = 0;
    for (int index=1; index < tree.length; index++) {

        depth[index] = 1;

        int parentIndex = tree[index];
        while (parentIndex != 0) {

            parentIndex = tree[parentIndex];
            depth[index]++;
        }
    }

    return depth;
}

Answer 1

在计算中，一次通过算法是一种只按顺序读取其输入一次的算法，没有无限缓冲(您不会将东西存储在别处并将其计为一次查看)。一次通过算法通常需要 O(n)(如果你有 n 个项目，它需要 n 个步骤才能完成)和少于 O(n) 的存储(因为你并不总是需要使用额外的存储，它可能很低O(1))，其中 n 是输入的大小。

(直接摘自 https://en.wikipedia.org/wiki/One-pass_algorithm ，带有一些外行翻译)

for 循环是一种典型的一次性算法 - 您只查看每个值一次，然后继续。 while 循环也可以工作，只要它只查看每个值一次并且不重复 for 循环查看的内容 - 但在这种情况下不是这样。

您在此深度优先搜索中的目标是只查看每个节点一次，然后继续前进，永不重复。 while 循环多次遍历树，所以不，它不是一次遍历。

希望这是有道理的。