问题标签 [complexity-theory]

我们都知道要保持简单，对吧？

我已经看到复杂性被衡量为系统之间的交互次数，我想这是一个很好的起点。除了直觉之外，还有哪些其他（最好是更客观的）方法可以用来确定特定设计或软件的复杂程度？

您最喜欢的规则或启发式方法是什么？

What is the clearest explanation of what computer scientists mean by "the naive implementation"? I need a good clear example which will illustrate — ideally, even to non-technical people — that the naive implementation may technically be a functioning solution to the problem, but practically be utterly unusable.

我们正在构建用于从网络中挖掘信息的工具。我们有几件，例如

• 从网络抓取数据
• 根据模板和业务规则提取信息
• 将结果解析到数据库
• 应用规范化和过滤规则
• 等等等等。

问题在于解决问题并对每个阶段发生的事情有一个很好的“高级图片”。

哪些技术帮助您理解和管理复杂的流程？

• 使用工作流工具，如 Windows Workflow Foundation
• 将单独的函数封装到命令行工具中并使用脚本工具将它们链接在一起
• 编写一种领域特定语言 (DSL) 来指定在更高级别上应该发生的事情的顺序。

只是好奇您如何处理具有许多交互组件的系统。我们希望记录/了解系统如何在比跟踪源代码更高的级别上工作。

假设您有一些数学背景，您将如何向天真者提供计算复杂性理论的一般概述？

我正在寻找 P = NP 问题的解释。什么是P？什么是NP？什么是 NP-Hard？

有时 Wikipedia 写得好像读者已经理解了所涉及的所有概念。

如果实用的量子计算成为现实，我想知道是否有任何基于 NP 完全问题的公钥密码算法，而不是整数分解或离散对数。

编辑：

请查看 关于量子计算机的 wiki 文章的“计算复杂性理论中的量子计算”部分。 它指出，量子计算机可以回答的问题类别（BQP）被认为比 NP-完全更容易。

编辑2：

“基于 NP 完全”是表达我感兴趣的东西的不好方式。

我想问的是一种公钥加密算法，其属性是任何破解加密的方法也可以用来破解潜在的NP完全问题。这意味着破解加密证明 P=NP。

什么是最坏情况时间复杂度 t(n) ：- 我正在阅读这本关于算法的书，并举例说明如何为 .... 获取 T(n)，例如选择排序算法

就像我正在处理 selectionSort(A[0..n-1])

让我写一个伪代码

--------我也会用C#写的----------------

===================

现在如何获得 t(n) 或众所周知的最坏情况时间复杂度

在讨论涉及散列和搜索类型的算法时，我注意到 O(1) 的一些非常奇怪的用法，通常是在使用语言系统提供的字典类型或使用数组使用的字典或散列数组类型的上下文中-索引符号。

基本上，O(1) 意味着以恒定时间和（通常）固定空间为界。一些非常基本的操作是 O(1)，尽管使用中间语言和特殊 VM 往往会扭曲这里的想法（例如，如何将垃圾收集器和其他动态过程摊销到 O(1) 活动中）。

但是忽略延迟、垃圾收集等的摊销，我仍然不明白如何假设某些涉及某种搜索的技术可以是 O(1)，除非在非常特殊的条件下。

尽管我之前已经注意到这一点，但Pandincus 问题中刚刚出现了一个示例，“'Proper' collection to use to get items in O(1) time in C# .NET?” .

正如我在那里所说，我所知道的唯一提供 O(1) 访问作为保证边界的集合是具有整数索引值的固定边界数组。假设是该数组是通过一些映射到随机存取存储器来实现的，该映射使用 O(1) 操作来定位具有该索引的单元格。

对于涉及某种搜索以确定不同类型索引（或具有整数索引的稀疏数组）的匹配单元格位置的集合，生活并不容易。特别是，如果存在冲突并且可能出现拥塞，则访问不完全是 O(1)。而且，如果集合是灵活的，则必须认识到并摊销扩展底层结构（例如树或哈希表）的成本，以缓解拥塞（例如，高碰撞发生率或树不平衡）。

我从来没有想过将这些灵活和动态的结构称为 O(1)。然而，我看到它们作为 O(1) 解决方案提供，而没有任何确定必须保持的条件才能确保实际具有 O(1) 访问（并且该常数小到可以忽略不计）。

问题：所有这些准备都是为了一个问题。O(1) 周围的随意性是什么？为什么如此盲目地接受它？是否认识到即使 O(1) 也可能非常大，即使接近恒定？还是 O(1) 只是将计算复杂性概念用于非正式使用？我很困惑。

更新：答案和评论指出了我自己定义 O(1) 的随意之处，我已经修复了它。我仍在寻找好的答案，在某些情况下，一些评论线程比他们的答案更有趣。

我了解 Big-O 表示法，但我不知道如何为许多函数计算它。特别是，我一直试图弄清楚斐波那契数列的原始版本的计算复杂性：

斐波那契数列的计算复杂度是多少，它是如何计算的？

REXX中length()函数的处理开销如何随字符串的长度变化？

更新：我正在使用：

• uni-REXX (R) 版本 297t
• Open-REXX (TM) 版权所有 (C) iX Corporation 1989-2002。版权所有。

我想了解有助于识别重叠数据集之间的共性和差异的算法信息。

以stackoverflow的标签系统为例：

假设这个问题被赋予了 5 个标签。假设有 1000 个其他问题至少具有这些标签之一。在这 1000 个问题中，有多少问题具有我的原始帖子所没有的共同标签？

另一种更简单的描述方式是自动建议标记系统：

“您用 [5 个我选择的标签] 标记了您的问题。其他类似的问题用 [可能感兴趣的标签列表] 进行了标记。其中 [可能感兴趣的标签列表] 是经常出现的标签，这些标签不在我的原始清单。

如果可能的话，c# 中的代码示例:)