Logn实际上是什么意思？

| 我正在为我的算法课程学习，并且一直在寻找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）来自哪里？对我的描述含糊不清，我感到很困惑。     
2019-12-18 6 条评论
分享

没有找到相关结果

    已邀请:

    疮痪徘弦漏

    如果考虑完整，平衡的二叉树，则逐层具有1 + 2 + 4 + 8 + ...顶点。如果树中的顶点总数为2 ^ n-1，则您有1 + 2 + 4 + 8 + ... + 2 ^（n-1）个顶点，逐层计数。现在，让N = 2 ^ n（树的大小），则树的高度为n，而n = log2（N）（树的高度）。这就是log（n）在这些Big O表达式中的含义。     
    2019-12-18 0 0
    分享

    凄嘛姥

    下面是一个示例树： 
          1
    /   \\ 
   2     3
  / \\   / \\
 4   5 6   7
    树中的节点数为7，但树的高点为log 7 = 3，当您使用除法和征服方法时，日志就会出现，以快速排序的方式将列表分为2个子列表，并继续进行此操作，直到生成丰富的小列表为止，除法花费了
    logn
    时间（通常情况下），因为除法的最高值为
    log n
    ，所以每个级别的划分都需要O（n），因为平均而言，每个级别中您划分的N个数字（可能有太多要划分的列表，但是平均数量是在每个级别中为N，实际上列表的一些计数为N）。因此，为了便于观察，如果您有平衡的分区树，则您有ѭ6的时间进行分区，这意味着树的高度。     
    2019-12-18 0 0
    分享

    旗低饶彤

    1秒钟忘掉b树 这里的数学：log2 N = k等于2 ^ k = N ..其对数的定义 ，则可以是自然log（e）N = k aka e ^ k = n，或者十进制log10 N = k是10 ^ k = n 2看完美，平衡的树 1个   1 + 1 1 +1 + 1 + 1 8个 16个 等等 有多少元素？ 1 + 2 + 4 + 8..etc，因此对于2层b树，有2 ^ 2-1个元素，对于3层树2 ^ 3-1等，所以这里是神奇的公式：N_TREE_ELEMENTS =级别数^ 2 -1，或使用log的定义：log2级别数= number_of_tree_elements（可以忘记-1） 3可以说有一个任务是在N个元素b树中找到元素，w / k级（也称为高度） b树的构造方式log2 height = number_of_tree元素 最重要的 因此，通过b树的构造方式，您只需要\'height \'操作即可在所有N个元素中查找元素，或者更少。.因此，高度等于：log2 number_of_tree_elements。 所以你需要log2 N_number_of_tree_elements ..或log（N）来缩短     
    2019-12-18 0 0
    分享

    埃输林桨铃

    要了解O（log（n））的含义，您可能想阅读Big O概念。在快照中，这意味着，如果您的数据集变得大1024倍，则运行时将仅长（或更少）10倍（对于基数2）。 MergeSort在O（n * log（n））中运行，这意味着将花费10 240倍的时间。冒泡排序以O（n ^ 2）进行，这意味着将花费1024 ^ 2 = 1 048 576倍的时间。所以确实有一些时间可以安全了:) 要了解您的总和，您必须将mergesort算法看成一棵树： 
             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非常满意，但就目前而言，这可能会让您更加困惑。这是非常理论性的，因此如果您不立即理解，请不要担心。     
    2019-12-18 0 0
    分享

    讹巳漓把备

    对我来说，要理解这样的问题，这是思考的好方法。     
    2019-12-18 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.040657043457031