Как вычислить время и пространственную сложность рекурсивной функции? - PullRequest
Новая
       82

Как вычислить время и пространственную сложность рекурсивной функции?

0 голосов
/ 25 января 2019

Я сейчас практикуюсь на собеседовании.Вопрос: 

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: 
    1. The root is the maximum number in the array. 
    2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
    3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Мое решение этого вопроса: 

def constructMaximumBinaryTree(nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if nums:
            maxIdx = nums.index(max(nums))
            root = TreeNode(nums[maxIdx])
            left = constructMaximumBinaryTree(nums[:maxIdx])
            right = constructMaximumBinaryTree(nums[maxIdx + 1:])
            root.left = left
            root.right = right
            return root

Я понимаю, как это работает, но я не уверен, как вычислить сложность времени и пространства.Если я попытаюсь вывести решение, входной массив будет разделен на две части для каждого узла, пока он не станет пустым.Итак, я предположил, что это будет что-то вроде O(log n), но я не уверен в точных рассуждениях.То же самое со сложностью пространства.Любые советы?

1 Ответ

0 голосов
/ 25 января 2019

Нет, это не обязательно O (n log n) .

Сначала рассмотрим сам процесс рекурсии: какова наихудшая (по умолчанию интерпретация «сложности») позициярешение о разделении? Если данный массив отсортирован, то максимальный элемент всегда находится в конце, и ваша рекурсия вырождается в процесс удаления одного элемента на каждой итерации.

Во-вторых, рассмотрим сложность одного проходачерез функцию, рекурсия в сторону. Какова сложность каждой операции в вашей последовательности?

  • find max списка
  • find элемент в списке
  • constructузел
  • список фрагментов
  • функция все
  • список фрагментов
  • вызов функции
  • назначение
  • назначение
  • возврат корневого узла

Многие из них O (1) операций, но некоторые из них O (n) - где nэто длина текущего списка, а не оригинала.

Thisв худшем случае O (n ^ 2) .Наилучший случай - O (n log n) , как вы интуитивно понимаете, учитывая идеально сбалансированное дерево в качестве входных данных.Средний случай ... вам, вероятно, это больше не нужно, но это O (n log n) с менее благоприятными константами.

...