问题标签 [complexity-theory]

可能重复：
是否有任何 O(1/n) 算法？

您的代码是否有可能是 Big O 小于 O(1)？

银行家算法用于确定是否可以满足所有对资源的请求而不会导致死锁。

m 是资源类型的总数

n 是进程总数

NEED 是一个大小为 m * n 的数组，它定义了每种资源类型的待处理请求。例如：NEEDij = 2 表示进程 i 正在请求 2 项资源 j。

算法如下：

我的问题是，时间复杂度如何为 0(n * n * m)？更具体地说，m 项如何进入多项式？是因为我们必须对长度为 m 的向量进行逐个元素的比较吗？

我正在使用 Ukkonen 的算法来构建后缀树，但我不理解作者对其线性时间复杂度的解释的某些部分。

我已经学习了算法并对其进行了编码，但是我用作主要信息来源的论文（链接如下）在某些部分有点令人困惑，所以我不清楚为什么算法是线性的。

有什么帮助吗？谢谢。

链接到 Ukkonen 的论文：http ://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

我使用的伪代码：

根据我的理解：

• 第 1 行：执行V-1次数。
• 第 2 行：所有顶点的度数之和时间......即2E时间

对于第 2 行：第 3 行和第 4 行需要时间，因为我们正在逐一log E添加/删除所有边缘。PQ

所以总计time= V-1+2E.logE=E.log E

但是书上说是这样E.logV，你能解释一下为什么会这样吗？

当我需要连接两个字符串时，我使用 String.Format （如果它发生在代码中的多个位置，则使用 StringBuilder）。

我看到一些优秀的程序员不会关注字符串连接的复杂性，而只是使用“+”运算符。

我知道使用“+”运算符会使应用程序使用更多内存，但是复杂性呢？

我是 Objective-C、Cocoa、Xcode 和 Interface Builder 的新手。我过去有一些 C 背景，以及相当多的 RealBASIC 经验。

我正在阅读 Mark 和 LaMarche 的 iPhone 3 Dev 书籍，我真的有点惊讶于有些事情是多么乏味。也许有人可以为我阐明这一点。我的问题真的是，为什么看似简单的动作的过程会涉及如此复杂的步骤？我以后会爱上的复杂性有什么好处吗？或者这只是一个无法避免的残酷事实？

例如，在 RealBASIC 中，如果我想在文本框中显示滑块的值，我只需添加：

到滑块的 Changed 事件。我可以在不到 1 分钟的时间内完成编程。

在 Xcode/Interface Builder 中，我必须为文本框和滑块键入一个声明，然后为每个都键入一个属性/出口声明，然后为 ValueChanged 创建一个方法声明和实现，然后设置一个（相对）使用 initWithFormat 将滑块的整数值复杂类型转换为 NSString。然后我必须返回到 Interface Builder 以将控件与我输入的控件和方法出口链接起来。我看不出这如何在不到 10 分钟的时间内完成。也许5。

那么，这样做有什么好处呢？为什么 Interface Builder 不自动创建或至少建议控件声明和@property 语句，以及方法声明和实现？为什么不能在 IB 中双击滑块为您提供事件列表并自动将框架方法插入到您的 .h 和 .m 文件中？为什么 IB 甚至必须是一个单独的应用程序？

我愿意接受其中一些是我对所有 Xcode 的不熟悉，但这真的和开发环境一样高效吗？

如果这是一个死马，火焰诱饵的话题，对立的双方都处于完全的仇恨状态，我深表歉意。如果是这样，请说“是的，就是这样”并继续前进。

谢谢，-罗伯

谁能告诉我这个函数的复杂度（Big O）是多少？

这实际上是我和我的一个朋友之间的争论。我的立场：复杂度是 O(n*log(n)) 朋友的立场：log(n)

感谢您的回复。

我正在阅读 Nicolai Josuttis 关于 C++STL 算法的书。对于stable_sort()等很多算法，他提到如果有足够的内存可用，算法的复杂度为n * log(n)，否则为n * log(n) * log(n)。我的问题是内存使用如何影响复杂性？STL 如何检测到这种情况？

在我们大学的离散数学课程中，老师向他的学生展示了阿克曼函数，并让学生在纸上开发该函数。

除了作为递归优化的基准之外，阿克曼函数还有什么实际用途吗？

我的小组正在对 for 循环构造进行一些讨论和强烈的感受。

我喜欢这样的循环：

但其他人似乎更喜欢布尔标志，如：

（并且，在语言允许的情况下，使用“for (int x = 0; ...”。)

第一种样式有一个更少的变量来跟踪和一个更简单的循环头。尽管以“重载”循环控制变量和（有些人会抱怨）使用 break 为代价。

第二种风格明确定义了变量的角色，但更复杂的循环条件和循环体（设置了 else 或 continue after found ，或循环平衡中的“if (!found)”）。

我认为第一种风格在代码复杂性上胜出。我正在寻找更广泛受众的意见。指向更容易阅读和维护的实际研究的指针会更好。“没关系，把它排除在你的标准之外”也是一个很好的答案。

OTOH，这可能是错误的问题。我开始认为正确的规则是“如果你必须打破一个 for，那真的是一段时间。”

执行前两个示例的操作，但行数更少。不过，它确实将 x 的初始化、测试和增量分成了三行。