我更喜欢尽可能少的正式定义和简单的数学.
algorithm complexity-theory big-o computer-science time-complexity
有时我看到Θ(n)带有奇怪的Θ符号,中间有一些东西,有时只有O(n).这只是打字的懒惰,因为没有人知道如何输入这个符号,或者它是否意味着不同的东西？
我问的更多关于这对我的代码意味着什么.我在数学上理解这些概念,我只是很难在概念上围绕它们的意思.例如,如果要对数据结构执行O(1)操作,我理解它必须执行的操作量不会增加,因为有更多项.而O(n)操作意味着您将对每个元素执行一组操作.有人可以在这里填空吗？
我听说有人说由于二进制搜索将搜索所需的输入减半,因此它是log(n)算法.由于我不是来自数学背景,所以我无法与之相关.有人可以更详细地解释一下吗？是否必须对对数系列做些什么？
我对big-O的了解是有限的,当日志术语出现在等式中时,它会让我更加惊讶.
有人可以用简单的语言向我解释O(log n)算法是什么吗？对数来自哪里？
当我试图解决这个中期练习题时,这个问题就出现了:
设X(1..n)和Y(1..n)包含两个整数列表,每个整数按非递减顺序排序.给出O(log n)-time算法以找到所有2n个组合元素的中值(或第n个最小整数).例如,X =(4,5,7,8,9)和Y =(3,5,8,9,10),那么7是组合列表的中位数(3,4,5,5,7) ,8,8,9,9,10).[提示:使用二分搜索的概念]
对于二进制搜索树类型的数据结构,我看到Big O表示法通常标记为O(logn).在日志中使用小写的"l",这是否意味着日志基数e(n)如自然对数所描述的那样？抱歉这个简单的问题,但我总是无法区分不同的隐含对数.
这有内置功能吗？
我被问到二元搜索是否是考试中的分而治之算法.我的回答是肯定的,因为你将问题分成了较小的子问题,直到你达到了结果.
但是检查员询问其中的征服部分在哪里,我无法回答.他们也不赞成它实际上是一种分而治之的算法.
但是我到网上的所有地方都说它是,所以我想知道为什么,以及征服它的部分在哪里？
algorithm computer-science binary-search divide-and-conquer data-structures
我是一个很长时间的潜伏者,只是接受了谷歌的采访,他们问我这个问题:
各种艺术家都想在皇家阿尔伯特音乐厅演出,你负责安排他们的音乐会.在大厅表演的要求按照先到先得的政策进行.每天只能进行一次演出,此外,不能在5天内举行任何音乐会
给定一个不可能的请求时间d(即在已经计划的性能的5天内),给出O(log n)时间算法以找到下一个可用日d2(d2> d).
我不知道如何解决它,现在面试已经结束,我很想知道如何解决它.知道你们大多数人的聪明才智,我想知道你能否在这里帮助我.这不是作业,或任何类似的东西.我只是想学习如何解决它以便将来的采访.我试着提出跟进问题,但他说这就是我可以告诉你的全部内容.
二进制搜索算法需要log(n)时间,因为树的高度(具有n个节点)将是log(n).
你会怎么证明这一点？