将二叉树(BT)转换为二叉搜索树(BST)的程序时间复杂度为何是nlogn

为什么该程序的整体时间复杂度为O(nlogn) #

这是由大O渐进时间复杂度的计算规则决定的：大O描述的是算法耗时随数据量增长的趋势，只需要保留增长速度最快的最高阶项，低阶项在数据量足够大时对整体量级的影响可以忽略不计。

我们先拆分所有步骤的时间复杂度：

• countNodes函数需要遍历全树所有节点统计数量，耗时O(n)
• storeInorder中序遍历存储节点值到数组，需要访问全树所有节点，耗时O(n)
• 调用qsort对数组排序，平均时间复杂度为O(nlogn)
• arrayToBST中序遍历将排序后的值写回树节点，同样需要访问全树所有节点，耗时O(n)

把所有步骤的耗时加总得到总耗时为：O(n) + O(n) + O(nlogn) + O(n) = O(nlogn + 3n)。当节点数n足够大时，nlogn的增长速度远快于线性的n项：比如n为100万时，nlogn大约是2000万，而3n仅为300万，二者的差距会随着n的增大越来越明显。

因此大O表示法会直接舍弃低阶的3n项，最终整体时间复杂度就和耗时最高的排序步骤一致，为O(nlogn)。

内容的提问来源于stack exchange，提问作者laxman prabha