需要我寫</p> <pre><code>while root ≠ null while hasChild(root) push(parentTree) ← root root ← pop(getChilds(root)) ... is parentTree isEmpty root ← null else root ← pop(parentTree) </code></pre> <p>一個僞

我需要確定的僞代碼的複雜性的複雜性我怎樣才能在最壞的情況下知道執行的數量（每行）？需要我寫</p> <pre><code>while root ≠ null while hasChild(root) push(parentTree) ← root root ← pop(getChilds(root)) ... is parentTree isEmpty root ← null else root ← pop(parentTree) </code></pre> <p>一個僞

我無法確定它，因爲我實際上不知道前兩行。之後，很容易，但我不知道前兩行的計數...

這是使用堆棧的樹實現，root是根節點，如您所見。

順便說一句，這是我第一次編寫僞代碼，所以我不確定我是否寫得很好。如果不正確，我可以重寫它。

來源

2012-02-01 Pier-Alexandre Bouchard

什麼是整體FUNC名稱？ pop（var）是什麼意思？通常pop只是pop（）。雖然僞代碼爲您定義事物（或不定義它們）提供了一些空間，但當東西像獨特的[]和insertLegend一樣出現時，很難猜測發生了什麼 – 2012-02-01 07:03:54

我刪除了「返回傳說」。它實際上是我需要分析的一個大算法的一部分。我只需要前兩行就可以了..我不知道如何確定它。 – 2012-02-01 07:06:45

我刪除了你不需要理解的部分。根有孩子，他的孩子也有孩子。所以pop（getChilds（root））實際上就是root.getChilds（）。pop（），它是根子節點的第一個子節點。 push（parentTree）是我需要在父樹中推送一個節點，parentTree在這裏。 – 2012-02-01 07:10:12

初步分析，我認爲在運行時O(logn*logn)

推理：外部時循環執行最多clogn次（其中c爲常數）。這是由於它依賴於'root'變量，而'root'變量反過來依賴於'pop parenttree' 父樹只能用'原始'根的孫輩填充。它最多會讓所有的孩子在樹上走一條路。其已知沿着樹的單個路徑的長度是logn

如果......不在O（1）中執行，則內部while循環也最多執行dlogn次（d是常數），然後它將實現在dlogn + X，和整體運行將是 O（LOGN *（LOGN + X）），有可能簡化到O(Xlogn)

假設IS是如果在if/else語句爲O運行（1）

外*內= O（clogn * dlogn）

來源

2012-02-01 07:28:51

需要我寫</p> <pre><code>while root ≠ null while hasChild(root) push(parentTree) ← root root ← pop(getChilds(root)) ... is parentTree isEmpty root ← null else root ← pop(parentTree) </code></pre> <p>一個僞

回答

相關問題