我对树木作业中的时间复杂有疑问.
据说(数据结构,Horowitz等)插入,删除,搜索,在BST中找到mins-maxs,后继节点和前驱节点的时间复杂度是O(h)AVL的那些时间复杂度O(logn).
我并不完全明白其中的区别.请h=[logn]+1记住,为什么我们说O(h)和其他地方一样O(logn)？
我正在研究合并排序主题,我遇到了这个概念,合并排序中的比较数(在最坏的情况下,根据维基百科)等于(n⌈lgn⌉ - 2⌈lgn⌉ + 1 ); 实际上它介于(n lg n - n + 1)和(n lg n + n + O(lg n))之间.问题是我无法弄清楚这些复杂性会说些什么.我知道O(nlogn)是合并排序的复杂性但比较的数量？