Logn究竟是什么意思？

Question

我正在为算法中的班级学习,并一直关注QuickSort.我理解算法及其工作原理,但不知道如何在一天结束时获得它所做的比较次数或登录实际意味着什么.

我理解基础知识,达到以下程度:

x=logb(Y) then
b^x = Y

但这在算法性能方面意味着什么呢？这是你需要做的比较的数量,我明白......尽管如此,整个想法似乎是如此难以理解.例如,对于QuickSort,每个级别的K调用都涉及2^k每个涉及长度子列表的调用n/2^K.

所以,总结找到比较的数量:

log n
? 2^k. 2(n/2^k) = 2n(1+logn)
k=0

为什么我们总结记录n？2n(1 + logn)来自哪里？很抱歉我的描述含糊不清,我很困惑.

Answer 1

下面是一个示例树：

      1
    /   \ 
   2     3
  / \   / \
 4   5 6   7

树中的节点数是7，但树的高度是log 7 = 3，当你有分而治之的方法时，log就会出现，在快速排序中，你将列表分成2个子列表，并继续这个直到丰富的小列表，划分需要logn时间（在平均情况），因为划分的最高点是log n，所以每个级别的划分需要 O(n)，因为每个级别平均划分 N 个数字，（可能划分的列表太多，但平均数字个数是 N在每个级别中，实际上一些列表的数量是 N）。因此，为了简单观察，如果您有平衡分区树，您就有log n时间进行分区，这意味着树的高度。