问题标签 [asymptotic-complexity]

是否有关于 .NET 集合类（等）的方法的渐近复杂性（big-O 和其他）的任何Dictionary<K,V>资源List<T>？

我知道 C5 库的文档包含一些关于它的信息（示例），但我也对标准 .NET 集合感兴趣......（并且 PowerCollections 的信息也很好）。

Big-O表示法O(n)和Little-O表示法有什么区别o(n)？

如果我有一个算法需要 n log n 步骤（例如 heapsort），其中步骤需要 log n 时间（例如比较/交换 0 到 n-1 范围内的“大”整数），那么整个过程。

显然我们可以说“n (log n) (log n)”，但我很难说服自己我不能将其简化为“n log n”。与此同时，我很难证明坚持认为我可以做到的本能。

我的直觉是完全错误的吗？

编辑

似乎我的简单示例避免使问题复杂化使问题复杂化。那好吧。

这个问题的真正原因是我经常有一个已知复杂度的标准算法，但使用不同的底层容器实现，因此各个步骤是 O(log n) 而不是 O(1)。例如，Hopcrofts 自动机最小化算法是 O(n log n) - 但是如果您开始使用二叉树容器来存储状态、转换和中间结果，那么步骤本身就会变成 O(log n) - O(n log n) 是不再有效，因为 O(1) 访问的假设是无效的。

尽管如此，人们仍会声称存在 n 个状态和 m 个转换，但是对于自动机，n 和 m 往往是线性相关的，假设转换注释的数量是恒定的并且自动机或多或少是确定性的。

过去我并没有太担心这一点——我处理的案例并不是很大。但是，好吧，我正在对我的自动机代码进行重大重构，我想我不妨在我进行时对一些关键算法进行正确的数学运算。

编辑

我也越来越相信“n (log n) (log n)”是错误的。

如果 a 是 O(b log b)，而 b 是 O(log c)，那么 a 与 c 的关系是多少？

如果我有一个算法需要 4n^2 + 7n 个动作来完成，它的 O 是多少？O(4n^2)? O(n^2)?

我知道 7n 被截断了，但我不知道我是否应该保留 n^2 系数。

谢谢

我试图解决给定的递归，使用递归树，T(n) = 3T(n/3) + n/lg n.

在第一层(n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3))。

在第二个级别它原来是n/(log(n/9))。

我可以将上面的方程概括为n.loglogn

这是我的普遍疑问，我需要对此有所了解。

注意：必须Theta(n^k log^k (n))在该函数 k 中的任何函数都应 >=1。在这种情况下 k 是 -1 所以主定理不会出现在图片中

合并算法通过重复比较两个输入数组的最小元素并将两个输入数组中较小的一个移动到输出，将两个排序的输入数组合并为一个排序的输出数组。

现在我们需要将三个相同长度的排序后的输入数组（A1、A2、A3）合并成一个（排序后的）输出数组，有两种方法：

1. 使用上述 Merge 算法将 A1 和 A2 合并到 A4 中，然后使用相同的算法将 A4 和 A3 合并到输出数组中。

2. 修改上述 Merge 算法，通过反复比较三个输入数组的最小元素，并将三个中最小的一个移动到输出数组。

如果仅考虑数组元素移动（即分配）的最坏情况，上述两种算法中哪一种更有效？

如果只考虑数组元素比较的最坏情况，上述两种算法中哪一种更有效？

在这两种算法中，哪一种在最坏情况下具有更高的整体效率？

通用编译器可接受的最大渐近运行时间是多少？

澄清：编译过程本身的复杂性，而不是编译程序的复杂性。例如，取决于程序大小，源代码字符、语句、变量、过程、基本块、中间语言指令、汇编程序指令或其他的数量。

这在很大程度上取决于您的观点，因此这是一个社区 wiki。

从编写编译器的人的角度来看这一点。当优化级别之一需要 O(n^6) 时，优化级别-O4是否会用于更大的程序？

相关问题：

• 何时可以接受超优化（指数复杂性甚至无法计算）？

• JIT可以接受什么？它必须是线性的吗？

• 已建立的编译器的复杂性是多少？海合会？风投？英特尔？爪哇？C＃？涡轮帕斯卡？低成本航空公司？LLVM？（参考？）

如果您不知道什么是渐近复杂度：您愿意等到编译器编译您的项目多长时间？（脚本语言除外）

它要求指出函数所属的类 Big-Theta(g(n)) 并证明断言。

在这种情况下 f(n) = (n^2+1)^10

根据定义 f(n) E Big-Theta(g(n)) <=> c1*g(n) < f(n) < c2*g(n)，其中 c1 和 c2 是两个常数。

我知道对于这个特定的 f(n)，Big-Theta 是 g(n^20)，但我不知道谁来正确证明它。我想我需要操纵这种不平等，但我不知道如何

我有一个性能问题，我怀疑一个标准 C 库函数花费的时间太长，导致我的整个系统（进程套件）基本上“打嗝”。果然，如果我注释掉库函数调用，打嗝就消失了。这促使我调查有哪些标准方法可以证明这种事情？测试一个函数以查看它是否会导致整个系统挂起一秒钟（导致其他进程暂时处于饥饿状态）的最佳实践是什么？

我至少想明确地关联被调用的函数和可见的冻结。

谢谢

是否有某种语言是 NP 完全的，但我们知道一些“快速”算法？我的意思不是像背包那样我们平均可以做得很好，我的意思是即使在最坏的情况下，运行时间也类似于 2^n^epsilon，结果对于任何 epsilon>0 都成立，所以我们可以让它任意接近0。