问题标签 [complexity-theory]

我想嵌入 3 个 NP-Complete 问题（其中 2 个已知是 NP-Complete，其中 1 个是我自己的想法）。我看到了“这个问题”，并在理论上重新解释了嵌入问题：

• 服务员就是小偷。
• 桌子是商店。
• 食物是具有不同重量的有价值的物品。
• 小偷在抢劫之前知道所有物品的价格和重量。
• 他的目标是最有效的抢劫（使用的背包的最大容量，获得最有价值的物品）抢劫（至少获得 1 件物品）所有商店（完成抢劫之旅的最短路径，也访问每个商店 1 次）。

这部分是嵌入 2 个 NP-Complete 问题。

我的想法是，更多的物品意味着更多的袋子重量。更大的袋子重量会成倍地减慢小偷的速度。所以小偷的另一个目标应该是尽快完成抢劫。

此时，我不确定我的想法是否真的是 NP-Complete。也许，“重力”不仅仅是一个 NP 完全问题。但也许是在旅行推销员和背包问题的背景下。

所以我的问题是：

1. 小偷NP的减速也完全吗？

2. 是否有可能将这三个嵌入式问题简化为一个简单的 NP 完全问题？

我今天在想什么可能是有史以来最复杂/最令人印象深刻的应用程序。所以我开始思考我每天都习惯和使用的数据库。

然后我进入了未知领域（我猜对我们大多数人来说），政府。我只能想象 NASA 应用程序的复杂性，这些应用程序允许他们与火星上的漫游者通信。

但后来我开始思考我从小就每天都在使用的东西，游戏。作为一名游戏开发者，这让我想到了大量关于人工智能和计算复杂性的问题，这些问题超出了我的想象。

游戏是最复杂/最令人印象深刻的应用程序吗？

什么是复杂性：

我知道它是 O(n^2) 但你如何计算这个？为什么不是 n*log n？

您是否使用您所使用的语言的调试器来单步调试代码以了解代码在做什么，或者您是否发现很容易查看其他人编写的代码以了解发生了什么？我说的是用 C# 编写的代码，但它可以是任何语言。

我刚刚接受了一个问题的采访，我很好奇答案应该是什么。问题本质上是：

假设您有一个未排序的 n 个整数列表。您如何找到此列表中的 k 个最小值？也就是说，如果你有一个 [10, 11, 24, 12, 13] 的列表并且正在寻找 2 个最小值，你会得到 [10, 11]。

我有一个 O(n*log(k)) 解决方案，这是我最好的，但我很好奇其他人想出了什么。我将通过发布我的解决方案来避免污染人们的大脑，并将在稍后对其进行编辑。

编辑#1：例如，类似的函数：list getMinVals(list &l, int k)

编辑#2：它看起来像是一个选择算法，所以我也会加入我的解决方案；遍历列表，并使用优先级队列来保存最小值。优先级队列的规范是最大值将在优先级队列的顶部结束，因此在将顶部与元素进行比较时，顶部将被弹出，较小的元素将被推送。这假设优先级队列有一个 O(log n) 推送和一个 O(1) 弹出。

你们发现所有算法在这两个方面都有惊人的（艰难的，奇怪的）复杂性分析 - 产生的 O 表示法和分析方式的唯一性？

我知道布尔可满足性是 NP-Complete 的，但它是布尔表达式的最小化/简化，我的意思是采用符号形式的给定表达式并以符号形式产生等效但简化的表达式，NP-Complete？我不确定从可满足性到最小化是否有减少，但我觉得可能有。有人有确切消息么？

我经常发现自己在与过度工程作斗争——负责设计软件的人提出的架构过于复杂。

拥有所有用户永远不会知道的深奥功能并获得成就感，当您做所有杂志文章都告诉您的最新，很酷的事情时，这一切都很好，但我们将花费我们在这座纪念碑上的一半工程时间是为了我们的聪明才智，而不是，你知道，我们的用户和高层管理人员期望在合理或至少有限制的时间框架内完成的实际产品。

当你开始用完时间时，你可能只需要恢复到更简单的解决方案，也就是说，如果你有机会的话。

我们都听过这样的副歌：保持简单，愚蠢™。

您如何应对团队中的过度复杂性？

最近我不得不反复使用的一个例子是，当决定采用完全非规范化的数据库设计而不是 RDBMS 时。“因为它更快！” 完全非规范化的数据库真的很难做到正确，并且只适用于像 Flickr 或 ebay 这样的真正专业的数据问题，并且相对于您的其余开发，这在开发人员时间方面可能非常昂贵。

我正在使用带有标题的数组。每个标题索引对应于数据库中的一个 id，其中包含该给定标题的 html。

假设我有一个包含其中一个标题的字符串。

要使用字符串“title”来获取相应的 id，我可以这样做：

我可以使用的另一种方法是创建一个关联数组以及与标题完全相反的标题数组。也就是说，它使用字符串作为索引并返回数字。

然后我可以通过以下方式访问 ID：

考虑到 CPU、内存等，什么最有效？

另外，如果我的逻辑完全错误，请告诉我。

谢谢威廉

我试图弄清楚如何给出最坏情况的时间复杂度。我不确定我的分析。我读过嵌套for循环 big O is n^2；for这对于内部有循环的循环是否正确while？

到目前为止，我有：

但我不确定我是否必须进入whileandfor循环来分析更坏的情况时间复杂度......

现在我必须证明它是紧束缚的，即 Big theta。

我读过嵌套for循环有 Big O of n^2. Big Theta 也是如此吗？如果不是，我将如何去寻找 Big Theta？！

**C1= C sub 1, C2= C sub 2, no= n naught 都是正实数的元素

为了找到T(n)我查看了的值j并查看了 while 循环执行了多少次：

分析：
对 while 循环执行求和，并认识到它是(n(n+1))/2 I 将其分配为我的T(n)，并证明它由n^2. 那是n(n+1)/2= θ(n^2)

从头开始工作：

公积金：

1. 证明 0 ≤ C1(n^2) 为真 C1(n^2)= n^2/2
   n^2/2≥ no^2/2
   ⇒no^2/2≥ 0
   1/2 > 0
   因此 C1 (n^2) ≥ 0 被证明是正确的！

2. 证明 C1(n^2) ≤ (n(n+1))/2 为真 C1(n^2) ≤ (n(n+1))/2
   n^2/2 ≤ (n(n+1 ))/2 n^2 ≤ n(n+1)
   n^2 ≤ n^2+n
   0 ≤ n

   我们知道这是真的，因为 n ≥ no = 1
   因此 C1(n^2) ≤ (n(n+1))/2 被证明是真的！

3. 证明 (n(n+1))/2 ≤ C2(n^2) 为真 (n(n+1))/2 ≤ C2(n^2)
   (n+1)/2 ≤ C2(n)
   n+1 ≤ 2 C2(n)
   n+1 ≤ 2(n)
   1 ≤ 2n-n
   1 ≤ n(2-1) = n
   1≤ n
   另外，我们知道这是正确的，因为 n ≥ no = 1

   因此，根据 1、2 和 3，θ(n^2 )= (n(n+1))/2 为真，因为
   0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2( n^2) 对于所有 n ≥ no

告诉我你们在做什么...我正在努力理解这些材料，并希望大家提供意见！