问题标签 [complexity-theory]

从我对语言设计的讨论来看，似乎很多人认为不存在也永远不会是“一种真正的语言”。根据这些人的说法，另一种选择是熟悉几种语言并为工作选择合适的工具。 这在整个项目或大型子项目的级别上非常有意义，只需通过非常狭窄、定义明确的界面与项目的其余部分进行交互。

另一方面，当试图优雅地解决许多小子问题时，使用许多不同的语言似乎是一件非常尴尬的事情。换句话说，恕我直言，在所有方面都不错的通用语言仍然很重要。作为一个简单的示例，假设您需要执行以下操作：

1. 从文件中读取一些任意格式的数据。检查它是否有错误等（最好在 Perl 之类的东西中完成）。
2. 将此数据加载到矩阵中，对其执行一堆核心矩阵操作（最好在 Matlab 之类的东西中完成）。
3. 在其上运行自定义的计算密集型例程，该例程必须快速且节省空间（最好在 C 或 C++ 中完成）。

这是一个相当简单的项目，除了编写计算密集型的自定义矩阵处理例程之外，但关于使用什么语言的唯一好答案似乎是一个通用的，在所有方面都不错。

我在这里想念什么？一个人如何有效地使用多种语言来充分利用它们的每一种优势？

有没有人使用单元测试来验证代码的时间/空间复杂度？

我更喜欢尽可能少的正式定义和简单的数学。

我会有一个很笼统的问题。除了在学校作为程序员之外，您是否曾经必须真正计算（例如在纸上）算法的复杂性？如果..你能给我一个例子吗？

谢谢你 ：）

在处理小型项目时，您认为将数据存储在简单的文本文件、哈希表等中与使用真实数据库相比，盈亏平衡点是什么？对于具有简单数据管理需求的小型项目，真正的数据库是不必要的复杂性，并且违反了 YAGNI。然而，在某些时候，数据库的复杂性显然是值得的。有哪些迹象表明您的问题对于简单的 ad-hoc 技术来说过于复杂并且需要一个真实的数据库？

注意：对于习惯于企业环境的人来说，这可能听起来像是一个奇怪的问题。但是，我的问题领域是生物信息学。我的大部分编程都是原型，而不是生产代码。我主要是领域专家，其次是程序员。我的大部分代码都是以算法为中心的，而不是以数据管理为中心的。这个问题的主要目的是让我弄清楚如果我学会在我的代码中使用适当的数据库而不是我通常使用的更多临时技术，从长远来看我可以节省多少工作。

The problem is the following:

You are given a set of positive integers { a1 , a2 , a3 , ... , an } in which there are no same numbers ( a1 exists only once ,a2 exists only once,...) eg A = {12 , 5 ,7 ,91 }. Question: Are there two disjoint subsets of A , A1 = { b1,b2,...,bm } and A2 = { c1,c2,...,ck} so that b1+b2+...+bm = c1+c2+...+ck ?

Note the following: It is not obligatory for A1 and A2 to cover A, so the problem isn't automatically reduced to the subset sum problem. eg A = {2,5,3,4,8,12} A1= {2,5} so sum of A1 is 7 A2= {3,4} so sum of A2 is 7 We found two disjoint subsets of A with the described property so the problem is solved.

How can I solve this problem? Can I do something better than find all possible (disjoint)subsets, calculate their sums and find two equal sums?

Thank you for your time.

我正在对各种 C++ 字典实现（地图、字典、向量等）进行报告。

使用 std::map 插入的结果表明性能为 O(log n)。性能也有持续的峰值。我不是 100% 确定是什么原因造成的；我认为它们是由内存分配引起的，但我未能找到任何文献/文档来证明这一点。

任何人都可以解决这个问题或指出我正确的方向吗？

干杯。

我需要计算以下代码的时间复杂度：

是O(n^2)吗？

什么是时间和空间复杂度：

它通过将 n 的值减 1 直到等于 1 来递归运行，然后它将 m 的值减 1 或在 m 等于 1 的情况下返回 1。

我认为复杂性取决于 n 和 m，所以可能是 O(n*m)。

给定一个 *n 大小的多头无环图，其中每个节点最多有三个子节点和三个父节点，是否存在一个非指数算法来识别是否存在一个 n 长度路径，其中没有两个节点共享相同的值，并且每个一个集合的值被占？

基本上，我有一个 n*n 迷宫，其中每个空间都有一个随机值 (1..n)。我需要找到包含每个值的 n 个节点的路径（从顶部到底部）。

现在我正在使用深度优先搜索，但那是T(n) = 3T(n-1) + O(1)一个O(3^n)非理想的解决方案。

确认我的恐惧，或指出我正确的方向将不胜感激。

编辑：为了让这个更具体一点，这里是一个带有解决方案的迷宫（使用深度优先解决方案解决）。