是否有一种简单的方法来确定语法是LL(1),LR(0),SLR(1)......只是从查看语法而不进行任何复杂的分析？
例如:要确定BNF语法是否为LL(1),您必须计算First和Follow集 - 在某些情况下这可能很耗时.
有谁知道如何更快地做到这一点？真的很感激任何帮助!
假设有一些数学背景,你会如何对天真的计算复杂性理论进行总体概述？
我正在寻找P = NP问题的解释.什么是P？什么是NP？什么是NP-Hard？
有时维基百科的编写就像读者已经理解了所涉及的所有概念一样.
Big-O表示法[1]在实践中失败的一些例子是什么？
也就是说:算法的Big-O运行时间何时会预测算法A比算法B快,但实际上算法B运行时会更快？
稍微宽泛一点:何时对算法性能不匹配的理论预测观察到运行时间？非Big-O预测可以基于搜索树中的平均/预期旋转次数,或者排序算法中的比较次数,表示为因子乘以元素的数量.
澄清:
不管有些答案的说法,大O符号是指预测算法的性能.也就是说,这是一个有缺陷的工具:它只谈论渐近性能,并且模糊了常数因素.这样做有一个原因:它意味着预测算法性能,而不依赖于您执行算法的计算机.
我想知道的是:这个工具的缺陷什么时候显示出来？我发现Big-O符号非常有用,但远非完美.有什么陷阱,边缘情况,陷阱？
我正在寻找的一个例子:使用Fibonacci堆而不是二进制堆运行Dijkstra的最短路径算法,得到O(m + n log n)时间对O((m + n)log n),对于n顶点和m边.你期望迟早会从斐波纳契堆中速度增加,但是在我的实验中说速度增加从未实现过.
(实验证据,没有证明,表明在均匀随机边缘权重上运行的二进制堆花费O(1)时间而不是O(log n)时间;这是实验的一个重要问题.另一个需要计算的婊子是预期的调用DecreaseKey的次数).
[1]真的不是失败的符号,而是符号所代表的概念,以及预测算法性能的理论方法.</抗炫学>
在接受的答案上:
我已经接受了一个答案来强调我希望的那种答案.许多不同的答案同样存在:)我喜欢的答案是,它建议了Big-O表示法"失败"时的一般规则(当缓存未命中占据执行时间时),这也可能增加理解(在某种意义上)我不知道如何最好地表达ATM).
首先,请注意,我感兴趣的是这样的东西是如何工作的,并且我不打算为客户端等构建它,因为我确信可能已经存在开源实现.
这些算法如何在上传文本中检测抄袭？它是否使用正则表达式将所有单词发送到索引,删除已知的单词,如"the","a"等,然后查看在不同的文章中有多少单词是相同的？他们是否有一些神奇的相同单词将它标记为可能的副本？它是否使用levenshtein()？
我选择的语言是PHP.
UPDATE
我正在考虑不在全球范围内检查抄袭,但更多的是在30个上传的论文中说.如果学生们在一个严格的一个人的任务上聚在一起.
这是一个声称这样做的在线网站:http://www.plagiarism.org/
我有一个有趣的问题,我一直试图解决最后一段时间:
我在2D xy平面上有3个圆圈,每个圆圈具有相同的已知半径.我知道三个中心的坐标(它们是任意的,可以在任何地方).
可以绘制的最大三角形是什么,使得三角形的每个顶点位于一个单独的圆上,这些顶点的坐标是什么？
我一直在看这个问题好几个小时并问了一堆人,但到目前为止只有一个人能够提出一个合理的解决方案(虽然我无法证明这一点).
我们提出的解决方案包括首先创建一个关于三个圆心的三角形.接下来,我们分别查看每个圆,并计算穿过圆的中心并垂直于相对边的线的方程.然后我们计算圆的两个交点.然后对接下来的两个圆进行,结果为6个点.我们迭代这6个点创建的8个可能的3个点三角形(限制是大三角形的每个点必须在一个单独的圆上)并找到最大尺寸.
结果看起来很合理(至少在纸上绘制时),它通过了圆的中心全部落在一条直线上的特殊情况(给出一个已知的最大三角形).不幸的是,我无法证明这是否正确.
我想知道是否有人遇到类似这样的问题,如果有的话,你是怎么解决的？
注意:我知道这主要是一个数学问题,而不是编程,但是它将在代码中实现,并且必须进行优化才能非常快速有效地运行.事实上,我已经在代码中进行了上述解决方案并进行了测试工作,如果您想看看,请让我知道,我选择不发布它因为它全部采用矢量形式而且几乎无法弄清楚到底是怎么回事(因为它被浓缩得更有效率).
最后,是的,这是为了学校的工作,虽然它不是一个家庭作业问题/任务/项目.这是我毕业论文的一部分(非常非常小的部分,但在技术上仍然是其中的一部分).
谢谢你的帮助.
编辑:这是我刚才想出的一种新算法.
从圆圈的中心开始,画一条线到另外两个中心.计算将所创建的角度平分的线,并计算圆与穿过圆心的线之间的交点.你将得到2个结果.对其他两个圆圈重复此操作以获得总共6个点.迭代这6个点,得到8个可能的解决方案.找到8种解决方案中的最大值.
如果您在三个点的一个"方向"上绘制线条,此算法将处理共线情况.
从我尝试使用CAD软件为我计算几何形状的少数随机试验来看,这种方法似乎优于之前所述的所有其他方法.但是,已经证明它不是Victor的反例之一的最佳解决方案.
我明天会对此进行编码,出于某种原因,我已经失去了对大学计算机的远程访问权限,而且大部分内容都在其上.
所以,让我们说你想学习一些关于数据库内部的东西.什么是最好的源代码？最好买的书？
我前几天和一个好友谈论这件事,他推荐:
计算机编程艺术,第3卷:排序和搜索
还有哪些书可以帮助我了解所有文件IO和内存问题,页面,锁定等等？
我刚遇到一个理论问题的时候了.
以下代码有效并编译:
public class Parent
{
public virtual object TestProperty { get; set; }
}
public class Child : Parent
{
private string _testValue = "Hello World!";
public override object TestProperty
{
get { return _testValue; }
}
}
public class Consumer
{
Parent p = new Child();
public Consumer(){ p.TestProperty = 3; }
}
我的问题是:
为什么C#允许我部分覆盖TestProperty孩子的auto属性,导致部分不可预测的行为？有实际应用吗？
我被允许使用父设置器设置TestProperty的值(我检查了生成的IL,并且设置器仍在父类中设置支持对象),即使公众无法访问值.