+ 2

Time complexity of decision 🌲 with base 2 and 3

Would the minimum number of iterations of any decision tree be the base itself in any symmetric decision tree eg. 3 root nodes with each root node having 3 child nodes recursively be the base itself ?

3rd Apr 2021, 7:06 AM
Sanjay Kamath
Sanjay Kamath - avatar
3 Réponses
+ 2
I didn't quite understand your question, but iterating through a full binary tree for example has time complexity Θ(2^n) where n is the depth of your tree. That's quite simply because the tree has 2^n elements. For a ternary tree that would be 3^n. Decision trees don't necessarily have the same number of children at each node, take chess for example. 20 possible moves on move 1 but many more later into the game.
3rd Apr 2021, 9:25 AM
Schindlabua
Schindlabua - avatar
+ 2
Schindlabua If there are 3 levels with the parent and each successive child having 3 nodes,the best evaluation can solve this in 27 log 3 = 3 perfect paths or choices 😀
3rd Apr 2021, 11:44 AM
Sanjay Kamath
Sanjay Kamath - avatar
+ 1
IMHO using balanced decision trees is. an algorithm optimization.... after àlpha beta pruning ... leads to better AI 🤗
4th Apr 2021, 1:56 AM
Sanjay Kamath
Sanjay Kamath - avatar