什麼是單程算法，是我的算法？

對於我正在上課的課程，最好使用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; 
}

來源

2017-09-19 Timmiej93

可能重複[什麼是單通道算法]（https://stackoverflow.com/questions/26322007/what-is-a-single-pass-algorithm） – PrestonM

你讀過[維基百科關於它的文章] （https://en.wikipedia.org/wiki/One-pass_algorithm）？什麼讓你感到困惑？ – Michael

我做過了，我也看過帖子說這可能是重複的，但對我來說，這些解釋相當複雜，帶來的混亂比確認更多。我認爲我的代碼是一次性的，但我不確定，因爲while循環。令我困惑的是使用（我猜）專業術語，這是我不熟悉的。 – Timmiej93

在計算，一個單程的算法是一個讀取它的輸入只有一次，爲了，沒有無限緩衝（你不會在其他地方存放東西和計數，作爲一個樣子）。一次性算法通常需要O（n）（如果您有n個項目，則需要n個步驟才能完成）和少於O（n）個存儲（因爲您並不總是需要使用額外的存儲空間，所以它可能很低作爲O（1）），其中n是輸入的大小。

（從https://en.wikipedia.org/wiki/One-pass_algorithm直擡起，一些外行翻譯）

for循環是一個典型的一個通算法 - 你在每個值看一次，以及繼續前進。 while循環也可以工作，只要它只查看每個值只有一次，並且不會重複for循環所看到的內容 - 但它不是在這種情況下。

您在這個深度優先搜索中的目標是精確地查看每個節點一次，然後繼續前進，從不重複。 while循環遍歷樹多次，所以不，它不是一次通過。

希望有道理。

來源

2017-09-19 15:21:28 Kwahn

很高興您編輯了您的答案。 –

因此，如果我理解正確：您只能訪問每個輸入（或在這種情況下輸入數組的變量）一次，並且不能將輸入存儲在其他臨時變量中？ – Timmiej93

是的，不會無限制地將輸入存儲在其他地方。你可以有一些但不是無限的方式 - 如果你需要在一個盒子中存儲一個變量，那沒問題，但是你不能以無限制的方式爲變量存儲創建更多的盒子。比如說，如果我總結一個數字列表，那麼中間結果就是一個有界的緩衝區（它只使用一個盒子，而不增長或縮小）。如果您決定將整個數據集存儲在另一個框中，那就不好，因爲它可能與您的數據集一樣大（它被認爲是無界的）。 – Kwahn

從外行的角度來說，一次通過算法就是按照順序只讀取一次輸入的算法。

您的代碼是否符合描述：否。

您tree多次與內側while循環遍歷輸入：

tree[index]和tree[parentIndex]

違反用於所述一個通算法的基本標準。

來源

2017-09-19 15:21:38

所以基本上，我只能使用1個單一的循環，從樹形數組中獲取每個值，我不能以任何其他方式訪問'樹形數組？' – Timmiej93

不一樣的索引。 –

什麼是單程算法，是我的算法？

回答

相關問題