标签: algorithm

有没有人知道什么是最简单的渐近减速,当编程纯粹功能而不是命令性(即允许副作用)时可能发生？

来自itowlson评论的澄清:有没有哪个问题最着名的非破坏性算法渐渐比最着名的破坏性算法更糟糕,如果是这样的话多少呢？

我需要一种方法来将多个字符串与测试字符串进行比较,并返回与其非常相似的字符串:

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW

CHOICE A   : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOICE B   : THE RED COW JUMPED OVER THE RED COW
CHOICE C   : THE RED FOX JUMPED OVER THE BROWN COW

(如果我这样做的话)最接近"TEST STRING"的字符串应该是"CHOICE C".最简单的方法是什么？

我计划将其实现为多种语言,包括VB.net,Lua和JavaScript.此时,伪代码是可以接受的.如果您可以提供特定语言的示例,这也是值得赞赏的!

我正在寻找创建一个图像基表,然后比较任何新图像,以确定新图像是否是基本的精确(或接近)副本.

例如:如果您想减少100次相同图像的存储空间,您可以存储它的一个副本并提供它的参考链接.输入新图像时,您想要与现有图像进行比较,以确保它不是重复的...想法？

我的一个想法是缩小到一个小缩略图,然后随机选择100个像素位置并进行比较.

假设我们有两个堆栈而没有其他临时变量.

是否可以仅使用两个堆栈"构造"队列数据结构？

我要检测两个时间段是否重叠.
每个期间都有开始日期和结束日期.
我需要检测我的第一个时间段(A)是否与另一个时间段(B/C)重叠.
在我的情况下,如果B的开头等于A的结尾,它们不重叠(反过来)
我发现以下情况:

所以实际上我这样做是这样的:

tStartA < tStartB && tStartB < tEndA //For case 1
OR
tStartA < tEndB && tEndB <= tEndA //For case 2
OR
tStartB < tStartA  && tEndB > tEndA //For case 3

(案例4在案例1或案例2中被记入帐户)

它有效,但似乎效率不高.

所以,首先在c#中有一个现有的类可以对此进行建模(一个时间段),类似于时间跨度,但具有固定的开始日期.

其次:是否已经有ac#代码(比如在DateTime类中)可以处理这个问题？

第三:如果不是,那么你最快速地进行这种比较的方法是什么？

检测有向图中所有周期的最有效算法是什么？

我有一个有向图表示需要执行的作业计划,作业是节点,依赖是边缘.我需要检测此图中循环的错误情况,从而导致循环依赖.

最近我一直在我的iPhone上玩一款名为Scramble的游戏.有些人可能认为这个游戏是Boggle.基本上,当游戏开始时你得到一个像这样的字母矩阵:

F X I E
A M L O
E W B X
A S T U

游戏的目标是尽可能多地找到可以通过将字母链接在一起形成的单词.你可以从任何字母开始,并且它周围的所有字母都是公平的游戏,然后一旦你继续下一个字母,围绕那个字母的所有字母都是合理的游戏,除了以前使用的任何字母.因此在上面的网格,例如,我能想出的话LOB,TUX,SEA,FAME,等词必须至少有3个字符,并且不超过N×N个字符以上,这将是本场比赛16,但可以在一些实现改变.虽然这个游戏很有趣且令人上瘾,但我显然不是很擅长它而且我想通过制作一个可以给我最好的单词的程序来作弊(单词越长,得分就越多).

样本博格http://www.boggled.org/sample.gif

遗憾的是,我不熟悉算法或效率等等.我第一次尝试使用字典,如这一个(〜2.3MB),并确实试图以配合字典条目组合线性搜索.这需要很长时间才能找到可能的单词,而且由于每轮只有2分钟,所以根本就不够.

我很想知道Stackoverflowers是否可以提供更有效的解决方案.我主要是在寻找使用Big 3 Ps的解决方案:Python,PHP和Perl,尽管Java或C++也很酷,因为速度至关重要.

当前的解决方案:

• Adam Rosenfield,Python,〜20年代
• John Fouhy,Python,~3s
• Kent Fredric,Perl,~1s
• Darius Bacon,Python,~1s
• rvarcher,VB.NET (实时链接),~1s
• Paolo Bergantino,PHP (实时链接),~5s(本地~2s)

BOUNTY:

我正在为这个问题增加一笔赏金,作为我向所有投入他们计划的人表示感谢的方式.不幸的是,我只能向你们中的一个人提供接受的答案,所以我将测量7天后谁拥有最快的晃动解算器,并奖励获胜者赏金.

赏金奖励.感谢所有参与的人.

我在接受采访时被问到这个问题.他们都是O(nlogn),但大多数人使用Quicksort而不是Mergesort.这是为什么？

我需要以下功能:

输入:alist

输出:

• True 如果输入列表中的所有元素使用标准相等运算符评估为彼此相等;
• False 除此以外.

性能:当然,我不希望招致任何不必要的开销.

我觉得最好是:

• 遍历列表
• 比较相邻元素
• 以及AND所有结果布尔值

但我不确定最恐怖的方式是什么.

编辑:

谢谢你所有的好答案.我评价了几个,而且很难在@KennyTM和@Ivo van der Wijk解决方案之间做出选择.

缺少短路功能只会对早期具有不相等元素的长输入(超过约50个元素)造成伤害.如果这种情况经常发生(通常取决于列表的长度),则需要进行短路.最好的短路算法似乎是@KennyTM checkEqual1.然而,它为此付出了巨大的代价:

• 高达20倍的性能几乎相同的列表
• 短名单上的表现高达2.5倍

如果早期不等元素的长输入没有发生(或很少发生),则不需要短路.然后,到目前为止最快的是@Ivo van der Wijk解决方案.

为了测试一个数字是否为素数,为什么我们必须测试它是否只能被该数字的平方根整除？