我只是在为我的算法课学习，并且一直在研究 QuickSort。我了解算法及其工作原理，但不了解如何在一天结束时获得它所做的比较次数，或者 logn 的实际含义。
我了解以下基础知识：
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
为什么我们总结为 log n ？2n(1+logn) 是从哪里来的？对不起，我的描述含糊不清，我很困惑。
如果您考虑一棵完整的平衡二叉树，那么逐层您有 1 + 2 + 4 + 8 + ... 顶点。如果树中的顶点总数为 2^n - 1，那么您有 1 + 2 + 4 + 8 + ... + 2^(n-1) 个顶点，逐层计算。现在，让 N = 2^n（树的大小），那么树的高度为 n，并且 n = log2(N)（树的高度）。这就是这些 Big O 表达式中 log(n) 的含义。
这里'数学：log2 N = k 相同 2^k=N .. 它是 log 的定义，它可以是自然 log(e) N = k aka e^k = n，或十进制 log10 N = k 是 10 ^k = n
1
1+ 1 1 + 1 + 1+ 1 8 个 16 个 等等
有多少元素？1+2+4+8..etc ，所以对于 2 级 b-tree 有 2^2-1 个元素，对于 3 级树 2^3-1 等等。所以这里有神奇的公式：N_TREE_ELEMENTS= 级数^ 2 -1 ，或者使用日志的定义：log2 number OF levels= number_of_tree_elements （可以忘记-1）
b-tree 的构造方式 log2 height = number_of_tree 元素
最重要的
因此，根据 b-tree 的构建方式，您不需要更多的“高度”操作来在所有 N 个元素中查找元素，或者更少。所以高度等于：log2 number_of_tree_elements ..
所以你需要 log2 N_number_of_tree_elements.. 或 log(N) 更短
下面是一个示例树：
1
/ \
2 3
/ \ / \
4 5 6 7
树中的节点数为 7，但树的高度为 log 7 = 3，当你有分而治之的方法时，log 出现，在快速排序中，你将列表分成 2 个子列表，并继续此操作直到丰富的小列表，划分需要logn时间（在平均情况），因为划分的高是log n，每个级别的分区需要O（n），因为在每个级别中您平均划分N个数字，（可能有太多列表用于分区，但平均数字是N实际上，在每个级别中，列表的一些计数是 N)。因此，对于简单的观察，如果您有平衡的分区树，您就有log n时间进行分区，这意味着树的高度。
要了解 O(log(n)) 的含义，您可能需要阅读Big O notaion。简而言之，这意味着，如果您的数据集大 1024 倍，那么您的运行时间只会长 10 倍（或更少）（对于基数 2）。
MergeSort 在 O(n*log(n)) 中运行，这意味着它将花费 10 240 倍的时间。冒泡排序在 O(n^2) 中运行，这意味着它将花费 1024^2 = 1 048 576 倍的时间。所以真的有一些安全的时间:)
要了解您的总和，您必须将合并排序算法视为一棵树：
sort(3,1,2,4)
/ \
sort(3,1) sort(2,4)
/ \ / \
sort(3) sort(1) sort(2) sort(4)
总和遍历树的每个级别。k=0 是顶部，k= log(n) 是底部。树的高度始终为 log2(n)（因为它是平衡的二叉树）。
做一个小数学：
Σ 2^k * 2(n/2^k) =
2 * Σ 2^k * (n/2^k) =
2 * Σ n*2^k/2^k =
2 * Σ n =
2 * n * (1+log(n)) //As there are log(n)+1 steps from 0 to log(n) inclusive
这当然需要做很多工作，特别是如果您有更复杂的算法。在这些情况下，您会为Master Theorem感到非常高兴，但目前它可能只会让您更加困惑。这是非常理论的，所以如果你不马上理解它也不要担心。
对我来说，要理解这样的问题，这是一个很好的思考方式。