下面算法的时间复杂度（O（n），O（n ^ 2）等）是多少[关闭]

Question

我和我的朋友想知道下面算法的时间复杂度是多少。我认为这是O（n），但他说这是O（n ^ 2）。我只是想要第二/第三/多少意见

def sorting(seq):

   T = BinarySearchTree()
   for i in seq:       #The insert function is part of the BST class and thus it
      T.insert(i)     #follows the rules for binary tree insertion.
   return inorder(T)   #This will return an inorder traversal of the newly 
                     constructed tree

Answer 1

正如你在评论中所说：

插入的时间复杂度最差为O（n）（插入偏斜的树中）

你为每个元素做了一次。

现在，如果你有理由相信最坏情况的摊销复杂性低于最坏情况下的个体复杂性（例如，插入几何增长数组的末尾，最坏的情况是O(n)但是我们知道每次O(n)时间我们只能遇到最坏的情况），事情有点复杂。但是没有理由相信这里。

因此，n插入物的总时间是n * O(n)，显然是O(n**2)。

由于inorder是线性时间，它不会添加任何东西; O(n**2 + n) == O(n**2)。

因此，根据您已经提供和提供的信息，您的朋友是对的。

而且你甚至已经弄清楚如何能够遇到这种最坏的情况：最大偏斜的树意味着每个插入物最终都会穿过整个链条。您应该能够非常容易地生成导致这种情况的病理数据，并明确地处理小案例。你正在做n*(n-1)/2比较，这是O(n**2)，所以我们在分析中没有出错。