6
मैं इस जावा विधि की पुनरावृत्ति सूत्रतलाश है: में आदेश द्विआधारी पेड़ उत्पादन विधि की पुनरावृत्ति फॉर्मूला
void printInorder(Node<T> v) {
if(v != null) {
printInorder(v.getLeft());
System.out.println(v.getData());
printInorder(v.getRight());
}
}
कुछ मापदंड के लिए खोज एक जाम का एक सा में हूँ:
- अपने एक पूरा द्विआधारी पेड़ (हर भीतरी गाँठ, 2 बच्चे हैं हर पत्ती उसी गहराई है)
- पेड़ n समुद्री मील और हे (एन) की एक जटिलता है
मुझे पेड़ के depth h के संबंध में n knots के साथ पुनरावृत्ति फॉर्मूला ढूंढना है, और एक अतिरिक्त बोनस के रूप में, मुझे उस से स्पष्ट सूत्र को निकालने की आवश्यकता है जो उस से ओ (एन) की ओर अग्रसर है।
अब, यह मैं क्या मिल गया है:
d = depth of the tree
c = constant runtime for execution of the method itself
d = 1: T(n) = c
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c
मैं उदाहरण घ = 3 इस्तेमाल किया खुद के लिए चीजों को स्पष्ट करने, मैं कठिनाइयों आगे इस टूट आ रही है। क्या मेरी धारणा भी सही है?
संपादित करें: बातें
[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number
d = 1: T(d) = 1
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1)))
1: T(h) = T(i = 0) + T(i = 1) + ... T(i = h-1)
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2)))
3: T(h) = n + n + ... + n
4: T(h) = (h-1)n
5: T(h) = O(n)
पेड़ की गहराई के हर स्तर के ठीक 2^(ज -1) नोड्स शामिल क्योंकि पर अगला प्रयास, लाइन 4 में ज कारक है क्योंकि अनदेखा किया जा सकता अंतिम परिणाम के लिए एन अधिक प्रासंगिक है।
