时间戳

首页 > 解决方案 > 我编辑的二叉搜索树get_size方法的时间复杂度

recursion - 我编辑的二叉搜索树get_size方法的时间复杂度

问题描述

我正在努力寻找我在二叉搜索树中创建的 get_size 方法的时间复杂度，因为存在多个条件的多次递归。这是代码

`class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.right = right
        self.left = left

    def __str__(self):
        return str(self.data)

我为库存数据创建了节点类，然后我创建了 BST 函数，它确实有效，但问题是每个函数的时间复杂度都应该是函数中的 log n，但我使用 if elif else 和双递归是否会影响运行时间 if它为什么如果它不为什么

class BST:
    def __init__(self):
        self.root = None

    def add(self, value, x=None):
        new_node = Node(value)
        if self.root is None:
            self.root = new_node
            return True
        if x is None:
            main_node = self.root
        else:
            main_node = x

        if value > main_node.data:
            if main_node.left is None:
                main_node.left = new_node
                return True
            else:
                return self.add(value, main_node.left)
        elif value == main_node.data:
            return False
        elif value < main_node.data:
            if main_node.right is None:
                main_node.right = new_node
                return True
            else:
                return self.add(value, main_node.right)

    def get_size(self, x=None):
        if self.root is None:
            return 0
        if x is None:
            main_node = self.root
        else:
            main_node = x
        if main_node.left is not None and main_node.right is not None:
            return 1 + self.get_size(main_node.left) + self.get_size(main_node.right)
        elif main_node.left is None and main_node.right is None:
            return 1
        else:
            if main_node.left is not None:
                return 1 + self.get_size(main_node.left)
            else:
                return 1 + self.get_size(main_node.right)`

标签： recursiontime-complexitybinary-treebig-obinary-search-tree

解决方案

为了确定复杂性，它有助于将您的功能分开并分别分析不同的部分。

从基本情况开始，您的复杂性是 O(1)。

if self.root is None:
    return 0

elif main_node.left is None and main_node.right is None:
    return 1

但是，随着您开始递归，这些基本案例将加起来。让我们看一个递归调用：

if main_node.left is not None and main_node.right is not None:
    return 1 + self.get_size(main_node.left) + self.get_size(main_node.right)

在最简单的树中，main_node左孩子和右孩子都是叶子，那么这两个对的调用get_size()将不再递归，导致两个 O(1) 操作。但是，如果任何一个节点都有子节点，那么我们将对 进行额外的调用get_size()，从而使结果get_size()大于 O(1)。如果左孩子有孩子，但那些孩子是叶子，那么我们将再调用get_size()两次，每次都是 O(1) 调用。

如果我们对函数中每个可能的 if/else 语句重复此分析，我们将看到对于每个存在的子节点，我们将调用get_size()它一次且仅一次。因此，我们的整体复杂度为 O(n)。

推荐阅读