大O符号计算机科学中的对数？
我一直有这个问题在脑海中，而且从来没有能够连接这两个概念，所以我正在寻找一些帮助理解计算机科学中的对数关于Big-O符号和算法时间复杂度的方法。 我将对数理解为一个数学概念，能够回答这个问题：“为了得到X，我需要用什么数来提高这个基数？”。 例如，log2（16）告诉我们，我们需要提高2到4次方才能得到16.我还有一个记忆级别的理解，即O（log n）算法比O（n）和其他较慢的算法因为那些是指数型的，并且O（log n）算法的一个例子是搜索平衡二叉搜索树。
我的问题有点难以确切说明，但我认为归结到为什么要寻找一个平衡的BST对数以及是什么使其成为对数的，以及我如何将数学对数与CS的使用联系起来？ 而后续问题是O（n log n）和O（log n）之间的区别是什么？
我知道这不是世界上最清晰的问题，但如果有人能帮助我将这两个概念联系起来，它就会为我清除很多困惑，并让我过去只是记忆（我通常讨厌）。
当您计算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]。
鉴于我们只有一个元素的工作清单，我们处于最坏的情况。 我们找到了该元素，或者它不存在于列表中。 我们只需要四步就可以确定这一点，看看7,3,1和0。
问题大小为16（列表中的元素数量），我们将其表示为N.在最坏的情况下，我们执行4次比较（2 ^ 4 = 16或16的Log base 2为4））。
如果我们看一个32的问题大小，我们只会进行5次比较（2 ^ 5 = 32或32的基准2为5）。
因此，BST的大O为O（logN）（注意，我们在CS中使用对数为2的基数）。
对于O（NlogN），最坏的情况是问题规模乘以对数的计算。 插入排序，快速排序和合并排序都是O（NlogN）的示例，
在计算机科学中，大O符号表示算法的操作次数在请求的问题陈述的给定参数n的情况下有多快。 在平衡二叉搜索树中，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 ），它本身比O（n log（n））快。
你的BST上有2 ^ n个叶子。 变量“n”是树的高度，或者以另一种方式变换多少次分支。 当你搜索时，你每次检查树分支。 所以你有对数时间。 （对数函数是指数函数的反函数）
链接地址: http://www.djcxy.com/p/39659.html上一篇: Logarithms in Computer Science for Big O Notation?
下一篇: Understanding Amortized Time and why array inserts are O(1)