What is a one-pass algorithm, and is mine one?

user_5721694 0
Viewed 6877

For a class I'm taking, it is preferred to use a one-pass algorithm to fix a certain task. Since this class is outside of my specialization (I'm Built Environment, the class is Computer Science), and it isn't discussed in class, I haven't got a clue what a one-pass algorithm is. Googling it gave made me think something like this:

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

For my code below, this suggests to me that the for loop would fit in a one-pass algorithm, but I'm unsure about the while loop.

Could you tell me, preferably in layman's terms, what a one-pass algorithm means / entails, and if my code below fits this description?

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;
}
algorithm java
2 Answers

In computing, a one-pass algorithm is one which reads its input exactly once, in order, without unbounded buffering (you're not storing things elsewhere and counting that as one look). A one-pass algorithm generally requires O(n) (if you have n items, it takes n steps to finish) and less than O(n) storage (since you don't always need to use extra storage, it could be low as O(1)), where n is the size of the input.

(lifted straight from https://en.wikipedia.org/wiki/One-pass_algorithm, with some layman translation)

A for loop is a quintessential one-pass algorithm - you look at each value exactly once and move on. A while loop can work too, as long as it only looks at each value exactly once and does not repeat what the for loop looks at - but it's not in this case.

Your goal in this depth-first search is to look at each node exactly once, and move on, never repeating. The while loop traverses the tree multiple times, so no, it is not one-pass.

Hope that made sense.

user_85485830

In layman terms, a one-pass algorithm is one which reads its input exactly once, in order.

Does your code fits the description: No.

You are traversing the input tree multiple times with the inside while loop:

tree[index] and tree[parentIndex]

which violates the basic criteria for the one-pass algorithm.

user_51508980
Related