我一直都有这个问题，并且从来没有能够将这两个概念联系起来，所以我正在寻找一些帮助来理解计算机科学中的对数关于Big-O表示法和算法时间复杂度 . 我将对数理解为能够回答问题的数学概念，"what number do I need to raise this base to exponentially to get X?" . 例如，log2（16）告诉我们需要将2增加到4才能得到16.我也有记忆级别的理解，O（log n）算法比O（n）和其他更慢的算法更快那些是指数的，并且O（log n）算法的一个例子是搜索 balancer 的二叉搜索树 .
我的问题有点难以准确说明，但我认为可归结为为什么搜索 balancer 的BST对数以及使其成为对数的原因以及如何将数学对数与CS的术语使用联系起来？后续问题是O（n log n）和O（log n）之间的区别是什么？
我知道这不是世界上最清楚的问题，但是如果有人可以帮助我将这两个概念联系起来，那么我就会清除很多困惑并让我超越记忆（我通常讨厌） .
3 回答
在计算Big O表示法时，随着问题规模的增大，您正在计算算法的复杂性 .
例如，在执行列表的线性搜索时，最糟糕的情况是元素在最后一个索引中，或者根本不在列表中，这意味着您的搜索将执行N个步骤，其中N是元素的数量在列表中 . 上） .
无论问题大小如何，总是需要完成相同步骤才能完成的算法是O（1） .
当您在算法中移动时，当您缩小问题大小时，对数会起作用 . 对于BST，您从列表中间开始 . 如果要搜索的元素较小，则只关注列表的前半部分 . 如果它更大，你只关注下半场 . 只需一步之后，您只需将问题大小减半 . 您继续将列表切成两半，直到找到元素或无法继续 . （请注意，二进制搜索假定列表是有序的）
让我们考虑一下我们在下面的列表中寻找0（BST表示为有序列表）：[0,1,2,3,4,5,6,7,8,9,10,11,12,13 ，14,15]
我们首先从中间开始：7 0小于7，所以我们看一下列表的前半部分：[0,1,2,3,4,5,6]
我们看一下这个列表的中间：3 0小于3，我们的工作清单现在是：[0,1,2]
所以我们看一下1. 0小于1，所以我们的列表现在是[0] .
鉴于我们只有1个元素的工作列表，我们处于最坏的情况 . 我们要么找到了元素，要么在列表中不存在 . 我们只用了四个步骤就可以确定这一点，看看7,3,1和0 .
问题大小为16（列表中的元素数），我们将其表示为N.在最坏的情况下，我们执行4次比较（2 ^ 4 = 16或16的基数2中的16是4）） .
如果我们看一下32的问题大小，我们只会进行5次比较（2 ^ 5 = 32或32的Log base 2为5） .
因此，BST的Big O是O（logN）（注意我们在CS中使用基数2作为对数） .
对于O（NlogN），最坏的情况是问题大小乘以其对数的计算 . 插入排序，快速排序和合并排序都是O（NlogN）的示例
在计算机科学中，大O表示法指示算法的操作数量随所请求的问题陈述的给定参数n增加的速度 . 在 balancer 二叉搜索树中，n可以是树中的节点数 . 在搜索树时，算法需要在树的每个深度级别做出决策 . 由于节点数量在每个级别加倍，树中节点的数量n = 2 ^ d-1，其中d是树的深度 . 因此，相对直观的是，算法采用的决策数是d-1 = log_ {2}（n 1）-1 . 这表明算法的复杂性是O（log（n））的阶数，这意味着操作的数量增长就像log（n） . 作为一个函数，日志增长慢于n，即当n变大时log（n）小于n，因此时间复杂度为O（log（n））的算法将比复杂度为O（n（n）的算法快 . ），它本身比O（n log（n））快 .
您的BST上有2 ^ n个叶子 . 变量“n”是树的高度，或以另一种方式进行，分支多少次 . 搜索时，每次都会检查树分支 . 所以你有对数时间 . （对数函数是指数函数的倒数）