algorithm - Improving the time complexity of DFS using recursion such that each node only works with its descendants -
problem
there balanced m-ary tree n levels deep. each inner node has m child nodes. root said @ depth 0 , leaf nodes said @ level n, there n ancestors of every leaf node. therefore, total number of nodes in tree is:
t = 1 + m^2 + ... + m^n = (m^(n+1) - 1) / (m - 1) here example m = 3 , n = 2.
(depth 0) _________|________ | | | b c d (depth 1) ___|___ ___|___ ___|___ | | | | | | | | | e f g h j k l m (depth 2) i writing depth first search function traverse entire tree in deepest node first , leftmost node first manner, , insert value of each node output list.
i wrote function in 2 different ways , want compare time complexity of both functions.
although question language agnostic, using python code below show functions because python code looks pseudocode.
solutions
the first function dfs1. accepts root node node argument , empty output list output argument. function descends tree recursively, visits every node , appends value of node output list.
def dfs1(node, output): """visit each node (dfs) , place value in output list.""" output.append(node.value) child_node in node.children: dfs1(child_node, output) the second function dfs2. accepts root node node argument not accept list argument. function descends tree recursively. @ every level of recursion, on visiting every node, creates list value of current node , descendants , returns list caller.
def dfs2(node): """visit nodes (dfs) , return list of values of visited nodes.""" output = [node.value] child_node in node.children: s in dfs2(child_node): output.append(s) return output analysis
there 2 variables define problem size.
- m -- number of child nodes each child node has.
- n -- number of ancestors each leaf node has (height of tree).
in dfs1, o(1) time spent while visiting each node, total time spent in visiting nodes is
o(1 + m + m^2 + ... + m^n). i don't bother simplifying expression further.
in dfs2, time spent while visiting each node directly proportional leaf nodes reachable node. in other words, time spent while visiting node @ depth d o(m^(n - d)). therefore, total spent time in visiting nodes is
1 * o(m^n) + m * o(m^(n - 1)) + m^2 * o(m^(n - 2)) + ... + m^n * o(1) = (n + 1) * o(m^n) question
is possible write dfs2 in such manner time complexity is
o(1 + m + m^2 + ... + m^n) without changing essence of algorithm, i.e. each node creates output list , descendants, , not have bother list may have values of ancestors?
complete working code reference
here complete python code demonstrates above functions.
class node: def __init__(self, value): """initialize current node value.""" self.value = value self.children = [] def add(self, node): """add new node child current node.""" self.children.append(node) def make_tree(): """create balanced m-ary tree depth n. (m = 3 , n = 2) 1 (depth 0) _________|________ | | | 2 3 4 (depth 1) ___|___ ___|___ ___|___ | | | | | | | | | 5 6 7 8 9 10 11 12 13 (depth 2) """ # create nodes = node( 1); b = node( 2); c = node( 3); d = node( 4) e = node( 5); f = node( 6); g = node( 7); h = node( 8); = node( 9); j = node(10); k = node(11); l = node(12); m = node(13) # create tree out of nodes a.add(b); a.add(c); a.add(d) b.add(e); b.add(f); b.add(g) c.add(h); c.add(i); c.add(j) d.add(k); d.add(l); d.add(m) # return root node return def dfs1(node, output): """visit each node (dfs) , place value in output list.""" output.append(node.value) child_node in node.children: dfs1(child_node, output) def dfs2(node): """visit nodes (dfs) , return list of values of visited nodes.""" output = [node.value] child_node in node.children: s in dfs2(child_node): output.append(s) return output = make_tree() output = [] dfs1(a, output) print(output) output = dfs2(a) print(output) both dfs1 , dfs2 functions produce same output.
['a', 'b', 'e', 'f', 'g', 'c', 'h', 'i', 'j', 'd', 'k', 'l', 'm'] ['a', 'b', 'e', 'f', 'g', 'c', 'h', 'i', 'j', 'd', 'k', 'l', 'm']
if in dfs1 output list passed reference, complexity of ds1 o(total nodes).
whereas, in dfs2 output list returned , appended parent's output list, taking o(size of list) each return. hence increasing overall complexity. can avoid overhead if both append , returning of output list takes constant time.
can done if output list "doubly ended linked list". hence can return reference of output list , instead of append can concatenate 2 doubly ended linked list (which o(1)).
Comments
Post a Comment