问题标签 [big-o]

根据关于链表的维基百科文章，在链表中间插入被认为是 O(1)。我认为这将是O（n）。您不需要找到可能在列表末尾附近的节点吗？

这种分析是否没有考虑到节点操作的发现（尽管它是必需的）而只是插入本身？

编辑：

与数组相比，链表有几个优点。在列表的特定点插入元素是一个常数时间操作，而在数组中插入可能需要移动一半或更多的元素。

上面的说法对我来说有点误导。如果我错了，请纠正我，但我认为结论应该是：

数组：

• 找到插入/删除点 O(1)
• 执行插入/删除 O(n)

链接列表：

• 找到插入/删除点 O(n)
• 执行插入/删除 O(1)

我认为唯一不必找到该位置的情况是，如果您保留某种指向它的指针（例如在某些情况下使用头部和尾部）。所以我们不能直截了当地说链表在插入/删除选项中总是优于数组。

我错过了介绍 big-O 的课程，认为它非常简单。然而，当 n 变得非常小时，老师似乎仍然说了一些关于 O(n) 偏离函数的内容？我在书中的任何地方都找不到这个。有人可以启发我吗？我们对 O(n) 的探索是在排序算法的背景下进行的，如果这有任何意义的话。

谢谢基因

编辑：感谢它一直以来的帮助。我有一个后续问题。是否有一种相对简单的数学方法来找出 n 对于 O(n) 而言太小的点？

相关问题

是否有任何 O(1/n) 算法？
Θ(n) 和 O(n) 有什么区别？

以下过程（解释如下）适用于非常小的列表，但是当列表包含大量项目（1/2 百万）时，应用程序进入“无响应”状态，大约需要 2.5 分钟才能完成（非常糟糕时间）。我可能会添加应用程序需要处理至少 1 亿个项目的列表（最终）。

这是有问题的过程的代码：

L 是一个长值列表。_subLists 是一个排序列表，其中每个值都是来自 L 的值的列表，开始一些差异（不相关）的算术级数系列。与该值关联的键是值包含的系列的长度。

例子：

L = {1,2,3,5,6,7,18,20,21} _subLists = {2,<20>} {3,<1,5>}

该过程只是从 L 中删除算术级数系列。

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

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

哪个需要更长的时间？

按排序顺序打印存储在二叉搜索树中的所有项目或按排序顺序打印存储在哈希表中的所有项目。

将哈希表的项目按排序顺序打印出来需要更长的时间，因为哈希表永远不会正确排序？BST 是什么？

为什么将 N 项插入空二叉搜索树 n^2 的最坏情况是 big-O？没有余额检查。

给定一个n词频对数组：

其中是一个词，是一个整数频率，频率之和，wifi∑fi = m

我想使用伪随机数生成器 (pRNG) 来选择p单词，以便选择任何单词的概率与其频率成正比：wj0, wj1, ..., wjp-1

（注意，这是带替换的选择，所以每次都可以选择同一个词）。

到目前为止，我已经提出了三种算法：

1. 创建一个大小为 的数组m，并将其填充为第一个条目是，下一个条目是，依此类推，所以最后一个条目是。f0w0f1w1fp-1wp-1

   然后使用 pRNG 选择prange 中的索引0...m-1，并报告存储在这些索引处的单词。
   这需要O(n + m + p)工作，这不是很好，因为m它可能比 n 大得多。

2. 遍历输入数组一次，计算

   在计算 之后，使用 pRNG为每个in生成一个范围内的数字， 并选择for （可能替换 的当前值） if 。 这需要工作。mixk0...mi-1k0...p-1wiwjkwjkxk < fi
O(n + np)

3. 按照算法 2 进行计算，并在 n 个词频部分和三元组上生成以下数组：mi然后，对于每个 k in ，使用 pRNG在范围内0...p-1生成一个数字，然后对三元组数组进行二进制搜索以找到st ，然后选择for 。 这需要工作。xk0...m-1imi-fi ≤ xk < miwiwjk
O(n + p log n)

我的问题是：有没有更有效的算法可以用于此，或者这些算法是否尽可能好？

这是场景。

我得到一个整数数组'A'。数组的大小不是固定的。我应该编写的函数可能会用一个只有几个整数的数组调用一次，而另一次，它甚至可能包含数千个整数。此外，每个整数不需要包含相同数量的数字。

我应该对数组中的数字进行“排序”，以使生成的数组具有按字典顺序排列的整数（即，它们根据它们的字符串表示进行排序。这里的“123”是 123 的字符串表示）。请注意，输出应该只包含整数，而不是它们的字符串等价物。

例如：如果输入是：

[ 12 | 第2434章 23 | 1 | 第654章 222 | 56 | 100000]

那么输出应该是：

[ 1 | 100000 | 12 | 222 | 23 | 第2434章 56 | 第654章]

我最初的方法：我将每个整数转换为其字符串格式，然后在其右侧添加零以使所有整数包含相同数量的数字（这是一个混乱的步骤，因为它涉及跟踪等使得解决方案效率非常低）然后做了基数排序。最后，我删除了填充的零，将字符串转换回它们的整数并将它们放入结果数组中。这是一个非常低效的解决方案。

我一直相信该解决方案不需要填充等，并且有一个简单的解决方案，您只需以某种方式处理数字（一些位处理？）即可获得结果。

您能想到的空间方面最有效的解决方案是什么？浪费时光？

如果您要提供代码，我更喜欢 Java 或伪代码。但如果这不适合你，任何这样的语言都应该没问题。

在任何情况下，并行化算法带来的不仅仅是线性速度的增加吗？

如何找到计算数组中和值的算法？

是这样的吗？

以及如何使用 O-Notation 将其与算法的运行时间联系起来

这是过去一年的考试，我需要为考试做修改。

问题给定一个包含
n 个整数值的数组 A[] 1.给出
一个计算数组中所有值之和的算法 2.找到
算法运行时间的最简单和最佳的 O 表示法。