问题标签 [big-o]

显然 ;-) 标准容器提供了某种形式的保证。

什么类型的保证以及不同类型的容器之间究竟有什么区别？

从SGI 页面工作（关于STL）我想出了这个：

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

我有一个列表更改列表 - 添加和删除。列表可能很大——比如 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)？

作为家庭作业，我得到了以下 8 个代码片段来分析并给出运行时间的 Big-Oh 符号。谁能告诉我我是否走在正确的轨道上？

我在考虑片段 1 的 O(N)

片段 2 也是 O(N)

片段 3 的 O(N^2)

片段 4 的 O(N)

片段 5 的 O(N^2) 但 n * n 让我有点失望，所以我不太确定

片段 6 也是 O(N^2)

片段 7 的 O(N^3) 但再次 n * n 让我失望

片段 8 的 O(N)

在以下情况下，我想知道 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)，为什么开发者会选择这样做呢？

我相信有一种方法可以在 O(n) 中找到长度为 n 的未排序数组中的第 k 个最大元素。或者也许它是“预期的” O(n) 或其他东西。我们应该怎么做？

比较 LinkedLists 和 Arrays，同时比较它们与已排序和未排序数据的差异

• 添加
• 移除
• 检索
• 排序
• 整体速度
• 总体内存使用情况

实际问题

讨论将未排序的数据集实现为链表而不是数组的可行性。在插入、删除、检索、计算机内存和应用程序速度方面的权衡是什么？

讨论将排序数据集实现为链表而不是数组的可行性。在插入、删除、检索、计算机内存和应用程序速度方面的权衡是什么？

根据您对前面问题的回答，总结在应用程序中使用链表的成本和收益。

我的答案/输入：

每次添加新节点时，LinkedLists 都必须分配内存，这在添加许多节点并且大小不断变化时很有用，但在添加少量元素时通常会变慢

数组在程序运行开始时分配内存，调整列表的速度很慢（如果必须调整大小，添加许多元素很慢）

由于索引，在数组中检索速度更快

由于指针，在 LinkedList 中添加/删除更快

范围相交是一个简单但不平凡的问题。

它已经回答了两次：

• 查找数字范围交点
• 比较日期范围

第一个解决方案是 O(n)，第二个解决方案是用于数据库（当然小于 O(n)）。

我有同样的问题，但是对于一个大的 n 并且我不在数据库中。

这个问题似乎与存储 2D 点以快速检索矩形内的点非常相似，但我看不出它是如何映射的。

那么，您会将范围集存储在什么数据结构中，以便对范围的搜索成本低于 O(n)？（使用可用于 Java 的库的额外功劳）

编辑：

我想获得所有相交范围的子集，这意味着搜索范围可以与多个范围相交。

Java中需要小于O(n)的方法是：

其中 Range 只是一个包含一对 int 开始和结束的类。

这不是一个不可能的问题，我已经有了解决方案，我只是想看看是否有更标准/更简单的方法