LogN的值是什么
Man*_*med 3 sorting algorithm big-o
因此，我一直在学习Big O符号（Noob），对我而言，大多数事情看起来像是外来语言。现在我了解了log的基本知识，例如base2的log 16是2的幂等于16。现在，对于二进制搜索大O（logN）对我来说毫无意义，那么LogN的值到底是多少？这里的底数是多少？我已经搜索过互联网，问题是每个人都用数学方式解释了这一点，我无法理解我对数学不满意。有人可以用基本英语而不是指数等外语向我解释这一点。我知道二进制搜索的工作原理。
第二个问题：[我什至不知道f =？（g）该符号表示什么]有人可以用纯白的英文给我解释这里需要什么，我不想要答案，这意味着什么。问题：在以下每种情况下，指示f = O（g）或f =？（g），或两者兼而有之。（在这种情况下，f ＝α（g））。
f(n) g(n)
（a）n-100 ...... n-200
（b）100n + logn ....... n +（log n）2
（c）log2n ...... log3n
更新：我刚刚意识到我研究了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表示法说明基数无关紧要，因此常数将被忽略。
在回答第二个问题时，图片将为您提供最好的解释。
大O仅与函数的上限有关。在下图中，f（n）= O（g（n））。换句话说，存在正常数c和k，使得0？f（n）？cg（n）对所有n？k。
- k的重要性在于，无论n的值是多少，在“ k”之后此Big O都将保持为真。如果我们不能固定'k'，就不能说增长率将始终低于O（...）中提到的函数。
- c的重要性是说O（...）之间的函数非常重要。
欧米茄就是大O的反演。如果f（n）= O（g（n）），则g（n）=？（f（n））。换句话说，？（）是你的函数停留上面什么是中提到的？（......）为另一“K”和其他“C”的给定值。
图片可视化是
最后，Big theta就是要找到一个数学函数，该函数以与给定函数相同的速度增长。但是如何证明此功能与您的功能相同。通过使用两个常量值。
由于它的运行方式与给定函数相同，因此您应该能够将两个常量“ c1”和“ c2”相乘，从而可以将c1 * g（n）置于函数f（n）之上，并将c2 * g（n ）放在函数f（n）下。
Big theta背后的功能是提供具有相同增长率的功能。注意，可能没有常数“ c”能够使f（n）和g（n）重叠。没人关心。唯一需要考虑的是能够使用两个常数将f（n）夹在ag（n）之间，这样我们可以自信地说我们找到了f（n）的增长率。
如何将以上学到的想法应用于您的问题？
让我们一个接一个地对待它们。您可以使用一些在线工具来绘制这些函数，并亲眼看看这些函数在沿数字线移动时的行为。
- f（n）= n-100和g（n）= n-200
在这里，可以通过区分两个函数wrt n来找出增长率。d（f（n））/ dn = d（g（n））/ dn =1。因此，即使f（n）和g（n）的运行时间可能不同，它们的增长率也相同。您可以选择'c1'和'c2'使得c1 * g（n）<f（n）<c2 * g（n）吗？
- f（n）= 100n + log（n）和g（n）= n + 2（log（n））
区分并告诉您是否可以将功能关联为Big O或Big Theta或Big Omega。
- f（n）=对数（2n）和g（n）=对数（3n）
同上。
（图像取自该网站的不同页面：http : //xlinux.nist.gov/dads/HTML/）
我的经验：尝试比较许多不同功能的增长率。最终，您将为所有这些人所掌握，并且对您来说将变得非常直观。经过一两个星期的集中努力，这个概念对任何人都无法保持深奥。