标签: complexity-theory

P = NP的问题可能是所有计算机科学中最着名的问题.这是什么意思？为什么它如此有趣？

哦,为了额外的功劳,请发表声明的真相或虚假证明.:)

我要显示log(n!)=Θ(n ·log(n)).

给出了一个提示,我应该用n ⁿ显示上限,并用(n/2)^(n/2)显示下限.这对我来说似乎并不那么直观.那为什么会这样？我绝对可以看到如何将n ⁿ转换为n ·log(n)(即记录等式的两边),但这种情况是向后的.

解决这个问题的正确方法是什么？我应该绘制递归树吗？这没有任何递归,所以这似乎不是一个可能的方法..

这里的二叉树可能不一定是二进制搜索树.
结构可以视为 -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

我可以和朋友一起解决的最大解决方案就是这种 -
考虑这个二叉树:

二叉树http://lcm.csa.iisc.ernet.in/dsa/img151.gif

顺序遍历产量 - 8,4,9,2,5,1,6,3,7

后序遍历产量 - 8,9,4,5,2,6,7,3,1

因此,例如,如果我们想要找到节点8和5的共同祖先,那么我们在顺序树遍历中创建8到5之间的所有节点的列表,在这种情况下恰好是[4,9] ,2].然后我们检查此列表中的哪个节点在后序遍历中最后出现,即2.因此,8和5的共同祖先是2.

这个算法的复杂性,我相信是O(n)(O(n)对于顺序/后序遍历,其余的步骤再次是O(n),因为它们只不过是数组中的简单迭代).但这很有可能是错误的.:-)

但这是一个非常粗略的方法,我不确定它是否会因某些情况而崩溃.这个问题还有其他(可能是更优的)解决方案吗？

我发现时间复杂度的资源还不清楚何时可以忽略时间复杂度方程中的项,特别是非多项式的例子.

我很清楚,给定n ² + n + 1 形式的东西,最后两个术语是无关紧要的.

具体来说,给定两个分类,2 ⁿ和n*(2 ⁿ),是第二个与第一个相同的顺序？额外的n乘法是否重要？通常资源只是说x ⁿ处于指数状态并且增长得更快......然后继续前进.

我可以理解为什么它不会因为2 ⁿ将大大超过n,但因为它们没有被加在一起,所以在比较两个方程时它会很重要,实际上它们之间的差异总是n的因子,这似乎至少可以说是重要的.

这可能听起来像一个愚蠢的问题,但我与我的一些开发人员进行了长时间的谈话,这听起来像是一件有趣的事情.

所以; 你的想法是什么 - 正则表达式是什么样的,永远不会被任何字符串匹配!

编辑:我为什么要这个？好吧,首先是因为我发现想到这样一个表达式很有趣,其次因为我需要它来制作一个脚本.

在该脚本中,我将字典定义为Dictionary<string, Regex>.如您所见,它包含一个字符串和一个表达式.

基于该字典,我创建的方法都使用这个字典作为他们应该如何完成工作的参考,其中一个匹配正则表达式与解析的日志文件.

如果表达式匹配,Dictionary<string, long>则为另一个表达式添加表达式返回的值.因此,为了捕获与字典中的表达式不匹配的任何日志消息,我创建了一个名为"unknown"的新组.

对于这个组,添加了与其他任何东西不匹配的所有内容.但是为了防止"未知"表达式(偶然)不匹配日志消息,我不得不创建一个绝对不会匹配的表达式,无论我给它什么字符串.

因此,你有理由这个"不是一个真正的问题"......

我们习惯说HashMap get/put操作是O(1).但是它取决于哈希实现.默认对象哈希实际上是JVM堆中的内部地址.我们是否确定声称get/putO(1)是否足够好？

可用内存是另一个问题.据我所知,从javadocs,HashMap load factor应该是0.75.如果我们在JVM中没有足够的内存且load factor超出限制怎么办？

所以,看起来O(1)似乎不能保证.它有意义还是我错过了什么？

我最近开始使用LINQ了,我还没有真正看到任何LINQ方法的运行时复杂性.显然,这里有很多因素在起作用,所以让我们将讨论局限于普通的IEnumerableLINQ-to-Objects提供者.此外,假设任何Func作为选择器/ mutator /等传入的是廉价的O(1)操作.

它似乎很明显,所有的单次操作(Select,Where,Count,Take/Skip,Any/All,等)将是O(n)的,因为他们只需要步行的顺序一次; 虽然这甚至会受到懒惰的影响.

对于更复杂的操作来说,事情变得更加模糊; 集合类运算符(Union,Distinct,Except等)使用工作GetHashCode在默认情况下(据我所知),所以它似乎是合理的假设他们使用一个哈希表内,使这些操作为O(n)为好,一般.使用的版本怎么样IEqualityComparer？

OrderBy需要排序,所以很可能我们正在看O(n log n).如果它已经排序了怎么办？如果我说OrderBy().ThenBy()并为两者提供相同的密钥怎么样？

我可以看到GroupBy(和Join)使用排序或散列.这是什么？

Contains将是O(n)on a List,但是O(1)on a HashSet- LINQ检查底层容器以查看它是否可以加快速度？

真正的问题 - 到目前为止,我一直坚信运营是高效的.但是,我可以依靠吗？例如,STL容器清楚地指定了每个操作的复杂性..NET库规范中的LINQ性能是否有类似的保证？

更多问题(回应评论):
没有真正想过开销,但我没想到对于简单的Linq-to-Objects有很多.CodingHorror帖子讨论的是Linq-to-SQL,在那里我可以理解解析查询并使SQL增加成本 - 对象提供者也有类似的成本吗？如果是这样,如果您使用声明性或功能性语法,它会有所不同吗？

此早期问题解决了可能导致算法具有O(log n)复杂性的一些因素.

什么会导致算法具有时间复杂度O(log log n)？

可能重复:
Θ(n)和O(n)之间有什么区别？

在我看来,当人们非正式地谈论算法复杂性时,他们谈论的是大哦.但是在正式情况下,我经常会看到偶尔出现大oh的大角色.我在数学上知道两者之间有什么区别,但在英语中,在什么情况下会使用大哦 - 当你的意思是大be时不正确,反之亦然(一个示例算法将不胜感激)？

额外奖励:为什么人们在非正式谈话时似乎总是使用大哦？

我很好奇O(n log n)是链表最好的.