大O和樹的遍歷

如果我有這樣的功能：大O和樹的遍歷

void myfunction(node* root) 
{ 
    for(int i = 0; i<root->children.size();i++) 
    { 
     myfunction(root->children[i]); 
    } 
}

請問這是n^2或N的大澳的大O？如果你有一個for循環，並且在循環裏面有一個函數調用自己，那麼大O函數的迭代次數是多少？

來源

2009-06-29 Jack Null

是的，我很樂意爲你做功課。感謝您的詢問。 – Eric 2009-06-29 13:48:02

在這裏有很多相似的線程：http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it，http://stackoverflow.com/questions/107165/大八十歲的孩子，http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o等。 – Groo 2009-06-29 13:48:20

它是O（n^98345984375743598734598734953752345）。 – 2009-06-29 14:27:05

這是一棵n-tree的按順序遍歷，但是你擊中了每一個元素，所以它是O（n）（big-theta更合適）。

來源

2009-06-29 13:47:40

新用戶詢問一個非常學術的問題=可能是功課。我希望你至少能夠理解爲什麼這是O（n）的基本原理。 – 2009-06-29 13:52:23

在數學，計算機科學和相關領域，大O符號描述了當參數趨於朝一個特定的值或無窮大，通常在簡單功能而言，具有功能的限制行爲。大O符號允許其用戶簡化功能，以便專注於他們的增長率：不同的功能與相同的增長率可用表示相同的O表示法。

其餘here。
關於你的例子，你肯定有O（n）。

來源

2009-06-29 13:48:57

這是O（n），其中n是節點的樹中的

來源

2009-06-29 13:49:31

它是一個遞歸函數調用的總數。您需要仔細研究遞歸關係以計算Big O符號的時間複雜度。你的推理在一般的情況下是正確的。在這個特定情況下，答案已經發布。

編輯：參考這個link關於Big-Oh遞歸函數的討論。

來源

2009-06-29 13:50:17

您可以通過考慮發生在具有N個節點的樹上的情況來解決這個問題。

該函數將針對樹中的每個節點調用一次，因此同時包含O（N）和Big-Theta（N）。

想一想，樹的寬度是多大，樹的高度是多大，它仍然具有相同的訪問次數。

即表示深度對寬度確實影響空間注意功能。

如果樹非常寬（比如說寬度爲深度對於任何N都是恆定的），那麼遍歷所需的堆棧空間是恆定的。
但是，如果寬度是一個固定常數值> 1，則所需的堆棧空間爲O（log（N））。
如果你有寬度爲1的退化情況，那麼樹就成爲一個鏈表，空間要求是O（N）。
一些語言/編譯器將能夠優化遞歸，以便空間需求實際上是恆定的（但這取決於你在做什麼/在遍歷期間返回）。

來源

2009-06-29 13:55:08 ShuggyCoUk

大O和樹的遍歷

回答

相關問題