Большая O сложность времени для двух вставок в массиве в цикле? - PullRequest
Новая
       15

Большая O сложность времени для двух вставок в массиве в цикле?

0 голосов
/ 01 декабря 2018

Каждая вставка в список python равна 0 (n), поэтому для приведенного ниже фрагмента кода наихудший случай - сложность времени O (n + 2k) или O (nk)?Где k - элементы, мы перемещаемся во время вставки. 

   def bfs_binary_tree(root):
     queue=[root]
     result=[]
     while queue:
          node = queue.pop()
          result.append(node.val)
          if node.left :
            queue.insert(0, node.left) 
          if node.right:
            queue.insert(0, node.right)
      return result

Я использую массивы в качестве очереди FIFO, но вставка каждого элемента в начале списка имеет сложность O (k), поэтому пытаюсь вычислитьиз общей сложности для n элементов в очереди.

1 Ответ

0 голосов
/ 02 декабря 2018

Поскольку каждый узел попадает в очередь не более одного раза, внешний loop будет выполняться n раз (где n - количество узлов в дереве).

Два вставкивыполняется во время каждой итерации цикла, и эти вставки потребуют size_of_queue + 1 шагов.

Таким образом, у нас есть n шагов и size_of_queue шагов в качестве двух представляющих интерес переменных.

Вопросявляется: размер очереди изменяется, так какова общая сложность во время выполнения?

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

Поэтому мы знаем, что алгоритм никогда не будет принимать больше, чем n * leaf nodes шагов.Это наша верхняя граница.

Итак, давайте выясним, каковы отношения между n и leaf_nodes.

Примечание: я предполагаю, что сбалансированный полный двоичный файлдерево

Количество узлов на любом уровне сбалансированного бинарного дерева с высотой не менее 1 (корневой узел) равно: 2^level.Максимальный уровень дерева называется depth.

Например, дерево с корнем и двумя дочерними элементами имеет 2 уровня (0 и 1) и, следовательно, имеет глубину 1 и высоту 2.

Общее число узлов в дереве (2^(depth+1))-1 (-1, потому что уровень 0 имеет только один узел).

n=2^(depth+1)-1

Мы также можем использовать этоотношение для определения глубины сбалансированного двоичного дерева, учитывая общее количество узлов:

Если n=2^(depth+1) - 1

n + 1 = 2^(depth+1)

log(n+1) = depth+1 = количество уровнейВ том числе и рут.Вычтите 1, чтобы получить depth (то есть, максимальный уровень) (в сбалансированном дереве с 4 уровнями уровень 3 является максимальным уровнем, поскольку корень - это уровень 0).

Что мыдо сих пор number_of_nodes = 2^(depth+1) - 1 depth = log(number_of_nodes) number_of_nodes_at_level_k = 2^k

Что нам нужно Способ получения числа конечных узлов .

Начиная с depth == last_level и начиная с number_of_nodes_at_level_k = 2^k, отсюда следует, что количество узлов на последнем уровне (конечных узлов) = 2^depth

Итак: leaf_nodes = 2^depth

Ваша сложность во время выполнения n * leaf_nodes = n * 2^depth = n * 2^(log n) = n * n = n^2.

...