insert - 找到插入 avl 树的复杂性

Question

如果我有一棵空avl树并且我想插入一组有序数字 (1, 2, ... k)，为什么复杂度是O(k).
谢谢你

Answer 1

这更像是一个数学问题，所以这是交易

AVL 树的时间复杂度为 log(n)，用于在树内插入具有 n 个节点的元素

所以从你的问题来看，你想插入一组数字 (1,2,3,...,k)，时间复杂度是这样的

summation from i=1 to i=k of log(i)（即 log1 + log2 + log3 + ... + logk）

这等于

log(k!)

这大约等于

k*log(k)（通过使用斯特林近似）

所以要回答你的问题，它应该是 O(k log k) 而不是 O(k)