什么是一种通用算法，是我的

Question

对于我要参加的类，首选使用one-pass algorithm来修复某个任务。由于该课程不在我的专业化之外（我是构建环境，这类是计算机科学），而且在课堂上没有讨论，所以我不知道一通算法是什么。谷歌搜索使我认为这样的事情：

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

对于下面的代码，这向我表明for loop适合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循环是一种典型的一通算法 - 您准确地查看每个值一次然后继续前进。a时循环也可以正常工作，只要它只能精确地查看每个值一次并且不会重复循环的内容 - 但在这种情况下不是。

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

希望这很有意义。

Answer 2

在外行术语中，一种通行算法是一种准确地读取其输入的算法。

您的代码适合描述： no 。

您正在使用内部while循环多次穿越输入tree：

tree[index]和tree[parentIndex]

违反了一通算法的基本标准。

Answer 3

我认为OP中的算法不是一个通用的算法，因为 tree 索引多次访问索引（一次又一次访问）。它可以用以下

之类的东西转换为一通

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];
        if(parentIndex != 0){
          depth[index] += depth[parentIndex]
        }
   }
   return depth;
}

在这里，我们正在计算孩子从已经计算的父母深度的深度。