问题标签 [complexity-theory]

我想知道可以使用哪种工具来测量 C 源代码的圈复杂度。

我看过其他帖子提出了同样的问题，但我只想知道 C 源代码的特定工具。

不仅仅是关于 LINQ to [在此处插入您最喜欢的提供程序]，这个问题是关于搜索或过滤内存中的集合。

我知道 LINQ（或搜索/过滤扩展方法）适用于实现IEnumerable或IEnumerable<T>. 问题是：由于枚举的性质，每个查询的复杂度至少是O(n)吗？

例如：

在这种情况下，每个算法至少需要O(n)，除非list是相对于 排序的'something'，在这种情况下，搜索应该是O(log(n))：它应该是二分搜索。但是，如果我理解正确，此查询将通过枚举解决，因此它应该采用O(n)，即使list之前已订购。

• 我可以做些什么来解决O(log(n))中的查询吗？
• 如果我想要性能，我应该使用 Array.Sort 和 Array.BinarySearch 吗？

在谈论算法的时间复杂度时，“恒定摊销时间”是什么意思？

我有一个列表更改列表 - 添加和删除。列表可能很大——比如 10,000 项。

我想知道更改 9'000 后列表的状态。

我可以从一开始就遍历列表以更改 9'000。这对我来说似乎有点啰嗦。

我可以保留一个项目列表并记录它们何时被添加和何时被删除，然后遍历此列表以查看列表中特定更改的内容。如果添加和删除的可能性相同，我将需要遍历的列表元素数量减半......

但是大 O 表示法表示，将问题的大小减半并不能提高效率（如果我理解正确的话）。

我可以在每 100 次或第 1000 次更改时缓存列表的状态……但是，大 O 再次表示，将项目数除以“n”并不能提高效率。

那么这样做的有效方法是什么？有没有一种有效的方法来做到这一点？

更多细节： 具体来说，我正在跟踪自定义分配器中的内存分配/释放。每个分配/解除分配都是列表中的一个事件。每个分配都有一个唯一的 ID。我想知道（例如）9'000 个事件之后当前分配的内容。

我的第一个想法是为每个 id 存储分配的事件和解除分配的事件。然后将此列表遍历到分配事件大于 9000 的第一个分配。但是就像我说的，这只会使我需要遍历的项目数量减半。

我喜欢 Mike F 提出的观点——从最近的第 100 个项目步行是恒定的时间......

我一直在完成最近的计算机科学作业，涉及递归和大 O 表示法。我相信我非常了解这一点（当然，当然不完美！）但是有一个问题特别给我带来了最多的问题。奇怪的是，看着它，它看起来是作业中最简单的一个。

使用 big-Oh 表示法提供最佳增长率来解决以下递归？

T(1) = 2

T(n) = 2T(n - 1) + 1 对于 n>1

选择是：

• O(n log n)
• O(n^2)
• O(2^n)
• O(n^n)

我知道大 O 用作上限，用于描述该程序或进程将花费的最多计算量或最长运行时间。我觉得这个特定的递归应该是 O(n)，因为对于每个 n 值，递归最多只发生一次。由于 n 不可用，它要么比这更好，O(nlogn)，要么更糟，成为其他三个选项。

所以，我的问题是：为什么不是 O(n)？

我目前正在完成一项处理 Big-O 和运行时间的任务。我向我提出了一个似乎很容易的问题，但我不确定我是否做得正确。其余的问题都相当困难，我觉得我在这里忽略了一些东西。

首先，你有这些东西：算法 A，它的运行时间为 50n^3。计算机 A，每次操作的速度为 1 毫秒。计算机 B，每次操作的速度为 2 毫秒。大小为 300 的实例。

我想知道算法 A 在计算机 A 上解决这个实例需要多长时间，以及在计算机 B 上需要多长时间。

我想要做的是低于 300 的 n，所以你有 50*(300^2) = 4500000。

然后，将第一台计算机乘以 1，第二台计算机乘以 2。

不过，这对我来说很奇怪，因为它说“运行时间”是 50n^3，而不是“操作次数是 50n^3”，所以我觉得我在乘以时间，并且会最终以毫秒平方为单位，这似乎根本不对。

我想知道我是否正确，如果不是，这个问题的实际含义是什么。

在编程中，我们面临需要使用中间 STL 容器的各种情况，如下例所示：

或者

考虑到 C++ 编译器的现状，哪种方法在时间和空间复杂度方面更好？

在以下情况下，我想知道 STL 多重集、映射和哈希映射类的 Big O 表示法的复杂性：

• 插入条目
• 访问条目
• 检索条目
• 比较条目

最近，我注意到有人提到它std::list::size()具有线性复杂性。
根据一些 消息来源，这实际上取决于实现，因为标准没有说明复杂性必须是什么。此博客条目中
的评论说：

实际上，这取决于您使用的是哪个 STL。Microsoft Visual Studio V6 将 size() 实现为 {return (_Size); } 而 gcc（至少在 3.3.2 和 4.1.0 版本中）将其作为 { return std::distance(begin(), end()); 第一个具有恒定速度，第二个具有 o(N) 速度

1. 所以我的猜测是，对于 VC++ 人群来说size()，复杂性是恒定的，因为 Dinkumware 自 VC6 以来可能不会改变这一事实。我在吗？
   
2. 它现在看起来像什么gcc？如果真的是O(n)，为什么开发者会选择这样做呢？

只是想知道有多少人在他们的应用程序中登录？？？

我见过这个：

“我通常喜欢使用 ERROR 日志级别来记录应用程序捕获的任何异常。我将使用 INFO 日志级别作为“第一级”调试方案，以便在我进入或退出方法时显示。从那里我使用DEBUG 日志级别来跟踪详细信息。FATAL 日志级别用于我在基于 Web 的应用程序中未能捕获的任何异常。

其中有这个代码示例：

但这似乎给方法增加了很多。例如，一个通常可能是 7 行代码的类突然变成了 12 行代码。该方法也失去了一些清晰性和简单性。

但话说回来，进行日志记录的好处可能是好的。例如，生产系统中的性能监控，追踪生产中的异常错误（并不是说您会一直打开所有这些日志记录。

因此，我想知道人们在做什么？干杯安东尼