问题标签 [complexity-theory]

我正在阅读 Aho、Hopcroft 和 Ullman 的“数据结构和算法”，我对练习 1.12 B 感到困惑：

这个 Pascal 过程的计算复杂度（用大 O 表示法表示）是多少？

请你帮助我好吗？

谢谢！

我正在使用民意调查：每个民意调查都有很多选项，用户可以在民意调查中投票一次。因此，我有一个包含以下字段的“投票”表：

• id（投票的id）
• option_id（所选投票选项的 ID）
• user_id（用户的id）
• poll_id（投票的id）

所以这就是我想要做的：给定一个 poll_ids 数组，我想让一个查询返回每个投票中投票最多的选项。因此，如果我给出 1 和 2 的 poll_id，我想取回投票 1 和 2 的投票最多的选项。我尝试了以下方法：

这几乎可以解决问题......但是为我提供的所有投票选项以及所提供的每个投票的相应投票，而不仅仅是投票最多的选项。如果有人有任何想法，我将不胜感激。谢谢。

我知道这更像是一个复杂性理论问题，而不是一个编程问题，希望我在这里没有做错事情，如果是错误的地方，我很抱歉，但我希望你们中的某个人有答案。它甚至在某种程度上与编程相关，因为它是一个复杂性理论问题。

我正在研究线性循环序列，我读到为了获得它弹出的序列的第 n 个值，你需要获得一些伴随矩阵的幂，我想知道是否有已知的算法来获得幂这种矩阵的快速方式..

我无法给出编码示例，但我会尝试为您提供更多解释：

k阶齐次线性循环序列：
s(n+k)=a(k-1)s(n+k-1)+a(k-2)s(n+k-2)+... +a(0)
for n=0,1,.. 其中 s(i) 是序列的第 i 个值，a(i) 是代数域中的系数。

A 是上述序列的伴随矩阵，如果它是：
( 0 0 0 0 ... 0 a(0) )
( 1 0 0 0 ... 0 a(1) )
( 0 1 0 0 ... 0 a (2) )
( .. .. .. .. .. .. .. .. ..)
( 0 0 0 0 ... 1 a(k-1) )
此外，理论指出，对于我们有序列：
s(n) = s(0)A^n for n=0,1,..
就是这样，感谢您的帮助。

给定范围 [0..n^3-1] 内的 n 个整数的输入集，提供线性时间排序算法。

这是我星期四测试的评论，我不知道如何解决这个问题。

正则表达式替换的复杂性问题接近问题，但并不相同。根据theprise的回复，（DFA引擎的）复杂度是：

O(2^m + n) [其中 m 是正则表达式的长度，n 是字符串的长度]

红皮书《算法设计手册》第15-16页讨论了不同算法的时间。据此，当算法长度超过 1,000,000 时，O(m^2) 的算法就没有希望了。处理时间为 16.7 分钟，假设运算时间为 1 纳秒。

书中的陈述增加了我的兴趣。你能在 16.7 分钟的处理时间内完成 1,000,000 个字符的正则表达式吗？你能做一个灾难性的正则表达式并且处理时间仍然存在吗？我真的很怀疑。

多项式时间内运算时间为一纳秒的最长可能正则表达式是多少？

好的快速概述

我研究过背包问题

http://en.wikipedia.org/wiki/Knapsack_problem

我知道这是我的项目所需要的，但我项目的复杂部分是我需要在一个主袋内有多个袋子。

装着所有“袋子”的大背包只能携带 x 个“袋子”（例如 9 个）。每个包都有不同的价值；

• 重量
• 成本
• 尺寸
• 容量

依此类推，所有这些值都是整数。让我们假设从 0-100。

内袋也将被分配一个类型，外袋中只能有一种类型，尽管程序输入将被赋予多个相同类型。

我需要指定主包可以容纳的最大重量，而小包的所有其他属性都需要按加权值分组。

例子

外袋：

• 可容纳 9 个较小的袋子
• 重量不超过 98 [两边各取 5 个]
• 每种必须持有一种，每次只能持有一种。

内袋：

• 成本，100% 加权
• 大小，权重为 67%
• 容量，权重为 44%

程序将输入多个袋子，然后必须计算出较小袋子的组合才能进入较大的袋子，根据输入会有多个解决方案，程序会为我输出最佳解决方案。

我想知道你们认为我解决这个问题的最佳方法是什么。

我将使用 Java 或 C# 对其进行编程。我很想用 PHP 对其进行编程，但我担心该算法对于 Web 服务器来说效率很低。

谢谢你提供的所有帮助

-扎克

对于一个拥有 1000 万玩家的在线扑克网站，描述合谋检测算法复杂性的最佳方式是什么？

假设（我认为这些假设没有太大区别，因此请随意忽略它们，但只是为了澄清）：

• 该网站拥有10,000,000个注册用户。
• 即这些玩家一共玩了50亿手牌。
• 您获得的唯一信息是该网站的“主手牌历史数据库”，其中包含所有玩家底牌和每手牌的下注动作。
• 换句话说，您可能不会走捷径，例如检查 IP 地址、寻找不寻常的抽水/盈利模式等等。
• 假设您有一个函数，当传递一组恰好 N（其中 N 在 2 到 10 之间）玩家时，如果该组中的所有玩家都串通在一起，则返回 TRUE。如果部分但不是所有玩家是共谋者，则该函数返回 FALSE。TRUE 的返回值是（例如）75% 的置信度。

Your job is to produce an exhaustive list of every player who's colluded, along with a complete list of the players he's colluded with. I have recently heard this problem described as NP-hard but is this accurate? Sometimes we call things "NP" or "NP-hard" that are merely "hard".

Thanks!

我对数据挖掘项目很感兴趣，并且一直想创建一个分类算法来确定哪些特定的签入需要代码审查，哪些可能不需要。

我已经为我的算法开发了许多启发式方法，尽管我还没有找出杀手...

如何以编程方式检查一段代码的计算复杂度？

此外，甚至更有趣 - 我如何不仅使用代码，还使用源代码控制存储库提供的差异来在那里获得更好的数据..

IE：如果我增加了我要签入的代码的复杂性——但它降低了剩下代码的复杂性——那不应该被认为是“好”的代码吗？

对您对此的想法感兴趣。

更新

显然我并不清楚。我要这个

双 codeValue = CodeChecker.CheckCode(someCodeFile);

我希望根据代码的好坏得出一个数字。当您计算复杂性时，我将从 VS2008 给出的数字开始，但想进一步探索。

有人有想法么？将不胜感激！

有谁知道LIKE最流行数据库的 SQL 运算符的复杂性是什么？

有人可以向我解释如何确定算法的最坏情况复杂性。我知道我们需要使用方程 W(n) = max{t(I)|I 的 D 元素)，其中 D 是大小为 n 的输入集。我是否计算为每个元​​素执行的操作次数，然后取其最大值？有什么更简单的方法可以做到这一点？