Блог пользователя checknmate

Time complexity in Divide and Conquer Approach
Автор checknmate, 27 часов назад, По-английски

Why do we assume the time complexity of any divide and conquer approach to be the number of level the tree has, should not it be the total edges in tree, like in case of merge sort we have logN, (not including the O(N) of merge since I had doubt regarding the tree).

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
26 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any genuine help by codeforcers ?

→ Ответить
  • »
    »
    26 часов назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    in devide and conquer you always traverse down the tree (from parent to one of the children) you never go from a child to a parent .And you stop when there no more children.

    That's what it means to traverse the levels of a tree .

    → Ответить
»
24 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I assume you're referring to tree divide/centroid decomposition.

The tree divide is based on you can process a vertex in $$$O(n)$$$ time, where $$$n$$$ is the size of the subtree. By selecting centroid every time, you can effectively cut down the size of the subtree.

The worst case of tree divide is when the tree is a link. You find the centroid and break the link into two $$$\frac{n}{2}$$$ links, and then four $$$\frac{n}{4}$$$ links, eight $$$\frac{n}{8}$$$ links and so on. That is to say, we have $$$O\left(n+2\cdot\frac{n}{2}+4\cdot\frac{n}{4}+\cdots\right)$$$ complexity. Since each link represents a vertex, the $$$1+2+4+\cdots$$$ term should be equal to $$$n$$$, so we have $$$\Theta(\log n)$$$ terms in the complexity formula, and each term is equal to $$$n$$$, so we have a $$$O(n\log n)$$$ complexity.

→ Ответить