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

Question

对于我正在上课的课程，最好使用 aone-pass algorithm来解决某个任务。由于这门课不在我的专业范围内（我是建筑环境，这门课是计算机科学），并且没有在课堂上讨论，我不知道什么是一次性算法。谷歌搜索它给了我这样的想法：

每个输入只能访问一次，并且所有内容都应按顺序处理。

对于我下面的代码，这向我表明for loop将适合 a one-pass algorithm，但我不确定while loop.

你能告诉我，最好用外行的话，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 循环多次遍历树，所以不，它不是一次遍历。

希望这是有道理的。