Большой O для этого рекурсивного алгоритма

Question

Я сделал следующий алгоритм, включающий структуру двоичной кучи:

Algorithm: heapMinimum(node)
Input    : Position n
Output   : Sequence minList; containing the postions that hold the minimum value

1. minList <-- sequence
2. if parent(node) == NULL // current node is the root of the tree
3.   minList.insertLast(node)
4. if (leftchild(node).element() == node.element())
5.   concat(heapMinimum(leftchild(node), minList))
6. if(right(node).element() == node.element())
7.   concat(heapMinimum(rightChild(node), minList))
8. return minList

Алгоритм выполняет в основном обход двоичной кучи по корню, чтобы найти и сохранить узлы с минимальным значением (т. Е. Значением, соответствующим корню).

Теперь у меня проблемы с вычислением времени выполнения в алгоритме Big O моего алгоритма. Причина, по которой я запутался, заключается в том, что рекурсия используется для обхода левого и правого потомков каждого узла.

Все операции выполняются в постоянное время, O(1), кроме concat. Но как мне точно рассчитать время работы такого рекурсивного решения?

Answer 1

Похоже, мне O (N), где N - количество элементов. Если ваша куча не содержит ничего, кроме равных элементов, все элементы будут пройдены. Кроме того, почему не concat O (1)? Пока вы «объединяете» числа, оно также должно быть O (1). Однако, если каким-то образом concat равен O (N) (из вашего псевдокода это выглядит так, как будто - но вы должны пересмотреть, если вам действительно нужно объединить два возвращенных списка), тогда общее время будет O (N ² ) худший случай.

Answer 2

Я полагаю, вы говорите о двоичной куче?

По определению свойств кучи, вы должны повторяться только до тех пор, пока не найдете элемент, который больше корневого. Однако вы также должны быть уверены, что ни один из других элементов на текущем уровне дерева не имеет такой же размер, как корень. По сути, это приводит к правилу, согласно которому, если вы встретите элемент кучи, превышающей корень, вам не нужно возвращаться к дочерним элементам.

Однако в худшем случае каждый элемент может быть равен корню. В этом случае вы должны проверить всю кучу, что дает время O (n), где n - количество элементов в куче.

Итак, чтобы ответить на ваш вопрос, это O (n)

Answer 3

Я полагаю, у вас есть ошибка в вашем решении. Первая проверка:

если родитель (узел) == NULL

необходимо удалить, но нужно добавить проверку, что узел! = NULL .

Более того, я предлагаю использовать список в качестве дополнительного параметра, в который вы положите ответ. Итак, это моя реализация:

Algorithm: heapMinimum(node, minList)
if (node != NULL)
{
   if (minList.empty() || minList.getFirst().element() == node.element())
   {
      minList.insertLast(node)

      heapMinimum(left(node),  minList)
      heapMinimum(right(node), minList)
   }
}

Предполагая, что добавление элемента в список занимает O (1), мы получаем, что функция принимает O (k), где k - количество минимальных значений в куче.

Наслаждайтесь.

Answer 4

Как уже упоминали другие, если ваш concat () равен O (1) [а если нет, вы можете сделать это так], тогда ваш алгоритм равен O (N) по размеру вывода.

Однако, если вы использовали concat (), который копирует ваш список (в зависимости от системы, это может быть легко сделать случайно), тогда ваш худший случай - O (N ^ 2) в размере вывода. Такое поведение возникает, когда ваши минимальные узлы уходят глубоко в дерево, так что ваш concat () продолжает копировать список на каждом уровне.

Обратите внимание, что эта глубина ограничена глубиной вашей кучи, поэтому, если ваше дерево сбалансировано, этот наихудший случай также равен O (M log M) в размере структуры данных. Вы можете видеть это, потому что максимальное количество копий - это глубина дерева.