LogN的价值是什么？
这个问题在这里已经有了答案：
更新：我刚刚意识到我研究了来自MIT视频的算法。 以下是这些视频中第一个的链接。 尽可能地继续下一次讲座。
显然，如果没有修正n是什么以及我们正在使用什么日志库，Log（n）就没有价值。 经常提到log（n）的目的是帮助人们理解特定算法或代码段的增长速度。 只有帮助人们从视角看事物。 要构建您的观点，请参阅下面的比较：
1 < logn < n < nlogn < n2 < 2^n < n! < n^n
上面的这条线表示，在数字线上的某个值n后，上述书面函数的增长率按照那里提到的顺序。 通过这种方式，决策者可以决定他们想要采取哪种方法来解决他们的问题（学生可以通过算法设计和分析考试）。
回答你的问题，当书上说'二分查找的运行时间是Log（n）'时，基本上它们意味着如果你有n个元素，二进制搜索的运行时间将与Log（n）成比例，并且如果你有17n元素，那么你可以期待你的算法在与Log（17n）成比例的持续时间内得到答案。 在这种情况下，Log函数的基数是2，因为在二进制搜索中，我们有<= 2路径可以从每个节点中选择。
因为，日志函数的基数可以很容易地通过乘以一个常数从任何数字转换为任何其他数字，告诉底层变得无关紧要，因为常量被忽略。
回答你的第二个问题，图像将解释最好的。
大O只是关于函数的上界。 在下图中，f（n）= O（g（n））。 换句话说，存在正常数c和k，使得对于所有n≥k，0≤f（n）≤cg（n）。
如果f（n）= O（g（n）），那么g（n）=Ω（f（n）），Omega就是大O的倒置。 换句话说，对于给定的另一个'k'和另一个'c'的值，Ω（）是关于你的函数保持在Ω（...）中提到的上面的函数。
图形可视化是
最后，Big theta是关于找到一个数学函数，它以与给定函数相同的速率增长。 但是，你如何证明这个函数和你的函数一样？ 通过使用两个常量值。
由于它与给定函数的运行方式相同，因此您应该能够乘以两个常数'c1'和'c2'，以便将c1 * g（n）置于函数f（n）之上并将c2 * g（n ）低于你的函数f（n）。
Big theta背后的事情是提供一个具有相同增长率的功能。 请注意，可能没有常数'c'，它将能够使f（n）和g（n）重叠。 没有人关心这一点。 唯一的问题是能够使用两个常数夹住ag（n）之间的f（n），这样我们可以自信地说我们找到了f（n）的增长率。
如何将以上学到的想法应用于您的问题？
让我们一个接一个。 您可以使用一些在线工具来绘制这些功能，并首先了解这些功能在沿着号码行时的行为。
在这里，增长率可以通过区分这两个函数来找出。 因此， 尽管f（n）和g（n）的运行时间可能不同，但它们的增长率是相同的 。 你可以选择'c1'和'c2'，使得c1 * g（n）<f（n）<c2 * g（n）？
区分并告诉你是否可以将这些功能作为Big O或Big Theta或Big Omega。
同上。
（图片来自本网站的不同页面：http://xlinux.nist.gov/dads/HTML/）
我的经验：尝试比较许多不同功能的增长率。 最终你会得到它的所有这些，它会变得非常直观。 鉴于集中精力一两个星期，这个概念对任何人来说都不可能是深奥的。
首先，我们来看看符号。 我从问题中假设O（f）是上界，Ω（f）是下界，Θ（f）是
对于这种情况下的O（log（N）），通常不给出基数，因为无论基数如何，log（N）的一般形式都是已知的。 例如，
日志（x）http://www.rapidtables.com/math/algebra/logarithm/log-graph.png
所以如果你已经完成了二分搜索算法（我建议你这样做，如果你没有），你应该发现最坏的情况（上限）是log_2（N）。 因此，给定N项，最坏情况下需要“log_2（N）计算”才能找到该项。
对于你的第二个问题，
你只是比较f和g的计算运行时间。
f = O(g)
当f是g的上界时，即f肯定需要比g更长的时间来计算。 交替，
f = Ω(g)
是当f是g的下界时，即g肯定会花费比f更长的时间来计算。 最后，
f = Θ(g)
是f在g上的上限和下限，即运行时间是相同的。
您需要比较每个问题的两个函数，并确定哪个计算需要更长的时间。 正如米奇提到的，你可以在这里检查这个问题已经被回答的地方。
编辑：意外链接e ^ x而不是日志（x）
从未指定日志的基础的原因是因为它实际上完全不相关。 你可以分三步说服自己：
首先回想一下log_2（x）= log_10（x）/ log_10（2）。 但是也要记住，log_10（2）是一个常数，我们称之为k2，所以真的，log_2（x）* k2 = log_10（x）
其次，回想一下，这不是唯一的基础2的日志。转换的常量不同，但所有的日志功能是通过乘法常数相互关联。
（如果您了解日志函数背后的数学，或者您可以在电子表格中快速处理它 - 您可以证明这一点 - 有一列log_2（x）和一列log_3（x）并将它们分开。 ）
最后，请记住，在Big Oh表示法中，常量基本上是不相关的。 试图区分O（log_2（N））和O（log_3（N））就像试图区分O（N）和O（2N）。 这是一个不重要的区别，因为log_2和log_3通过常量关联。
老实说，日志的基础并不重要。
链接地址: http://www.djcxy.com/p/40019.html上一篇: What is the Value of LogN
下一篇: th key in a B