Почему время выполнения этого алгоритма O (t)? - PullRequest
Новая
       39

Почему время выполнения этого алгоритма O (t)?

1 голос
/ 24 июня 2019

Это из проблемы 4.8 из Cracking the Coding Interview 6th edition. Следующий код является одним из решений следующего приглашения: «Найти первого общего предка двух узлов в двоичном дереве» 

TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
/* Checks if either node is not in the tree, or if one covers the other. */
   if(!covers(root, p) || !covers(root, q)){
      return null;
   } else if (covers(p,q)){
      return p;
   } else if (cover(q,p)){
      return q;
   }

   /* Traverse upwards until you find a node that covers q. */
   TreeNode sibling = getSibling(p);
   TreeNode parent = p.parent;
   while(!covers(sibling, q)){
    sibling = getSibling(parent);
    parent = parent.parent;
   }

   return parent;
}

boolean covers(TreeNode root, TreeNode p){
   if(node == null) return false;
   if(root == p) return true;
   return covers(root.left, p) || covers(root.right,p);
}

TreeNode getSibling(TreeNode node){
   if(node == null || node.parent ==null){
     return null;
   }

   TreeNode parent = node.parent;
   return parent.left == node ? parent.right: parent.left;

}

В книге говорится, что "этот алгоритм занимает время O (t), где t - это размер поддерева для первого общего предка. В худшем случае это будет O (n)"

Однако, это не вызовы обложек от root в начале commonAncestor, делающие время выполнения O (d + t), где d - это глубина либо p, либо q, в зависимости от того, какой из них глубже.

Ответы [ 2 ]

1 голос
/ 24 июня 2019

Похоже, что cover(root,p) будет искать все поддерево с корнем в x, так как проверяет root.left и root.right рекурсивно.

Но да, эту проблему можно решить за время O (d). (Поднимитесь от каждого из p, q к корню, а затем просто к первому элементу, который объединяет два списка.)

Хм, похоже, что код внутри cover тоже неверен, по-разному:

  • он, вероятно, хочет return false вместо return null, когда мы вернулись "с конца" ветви;
  • еще более хлопотно, он должен проверить, что иногда он находит цель: if (root==p) return true. (Можно быть умным и изменить существующий оператор return на return (root==p) || covers(..,..) || covers(..,..).)
0 голосов
/ 25 июня 2019

Возможно, вы захотите просмотреть часть о Big O в начале книги. O (d + t) является несколько точным, но потому что это плюс один из них (или d или t) будет расти быстрее, чем другой. В этом случае t = количество узлов в поддереве и d = глубина во всем дереве. Т будет расти значительно быстрее, чем д.

В качестве иллюстрации: 

      1
    /   \
  2       3
 / \     / \
4   5   6   7

If We're looking at this tree and we want to know the common ancestor for 4 and 5:
  t = 3
  d = 3
if we want the common ancestor of 2 and 7 in the same tree then:
  t = 7
  d = 3

В связи с тем, что глубина работы деревьев всегда будет равна или меньше количества узлов. Следовательно, временная сложность будет средней (большая тета?) Из t (количество узлов в поддереве) и в худшем случае (большое o) n (количество узлов в дереве).

Кроме того, проверки root будут выполнять O (n) в начале, что сделало бы все O (n), но автор заявляет, что на самом деле оно имеет O (n). «этот алгоритм занимает время O (t)», я думаю, авторский анализ для среднего случая.

...