问题标签 [big-o]

我还没有看到任何东西，我怀疑定义“n”有困难，因为通常用于分析复杂函数的定义不止一个或两个变量。

有用于圈复杂度的分析工具，但是否有用于时间（和/或空间）复杂度的分析工具？如果是，是哪些，如果不是，为什么不呢？不可行吗？不可能的？只是有人没有解决它吗？

理想情况下，应用程序的整体复杂性（定义不同的可能“n”）以及应用程序中的每个方法

编辑：因此，由于停机问题，似乎不可能有一个精确的解决方案，但是，某种启发式近似是否可能？我意识到，出于实际目的，一个好的分析器会提供更多有用的信息，但这似乎是一个有趣的问题。

另外，一个计算某个程序子集的程序怎么样？

我正在使用带有标题的数组。每个标题索引对应于数据库中的一个 id，其中包含该给定标题的 html。

假设我有一个包含其中一个标题的字符串。

要使用字符串“title”来获取相应的 id，我可以这样做：

我可以使用的另一种方法是创建一个关联数组以及与标题完全相反的标题数组。也就是说，它使用字符串作为索引并返回数字。

然后我可以通过以下方式访问 ID：

考虑到 CPU、内存等，什么最有效？

另外，如果我的逻辑完全错误，请告诉我。

谢谢威廉

我正在阅读 Aho、Hopcroft 和 Ullman 的“数据结构和算法”，我对练习 1.12 B 感到困惑：

这个 Pascal 过程的计算复杂度（用大 O 表示法表示）是多少？

请你帮助我好吗？

谢谢！

我已经看到这个术语“O(1) 访问时间”曾经表示“快速”，但我不明白它是什么意思。我在同一上下文中看到的另一个术语是“O(n) 访问时间”。有人可以用简单的方式解释这些术语的含义吗？

也可以看看

• 什么是大 O 符号？你用它吗？
• 八岁的Big-O？

我对数据库很陌生，所以如果这是一个愚蠢的问题，请原谅我。

在现代数据库中，如果我使用索引来访问一行，我相信这将是 O(1) 复杂度。但是，如果我进行查询以选择另一列，它将是 O(1) 还是 O(n)？数据库是否必须遍历所有行，还是为每一列构建一个排序列表？

我的问题来自“Big O 的简单英语解释”一文。我不知道对数复杂度的确切含义。我知道我可以在时间和操作次数之间进行回归并计算 X 平方值，从而确定复杂度。但是，我想知道一种在纸上快速确定它的方法。

你如何确定对数复杂度？有一些好的基准吗？

在大学里学习了所有关于计算算法成本的知识，但那是很久以前的事了，我都忘记了。有没有贯穿整个主题的演练？我觉得好像比我现在记得的要多。我想刷新我的一些核心技能。

根据我读过的书，这段代码应该是O((n^3)/4)。但显然不是。要找到嵌套循环的 Big-O，你应该乘以界限吗？所以这个应该是 num *n *n 或 n/4 *n *n。

我是德国计算机专业的学生。我的教授给出了以下问题来思考：

'给定对单个链表中节点的引用（不是最后一个节点）。给出一个算法从列表中删除这个元素，它具有 O(1) 复杂度，同时保持完整性。

我想过这个，但我很确定，没有这样的算法。因为它是一个单链表，你必须遍历链表中的每个节点，直到你到达应该删除的节点，因为你必须在删除之前修改节点中的下一个指针。这将导致 O(n) 复杂度。

我错过了什么吗？

根据维基百科关于动态数组的文章，在数组末尾插入/删除是 O(1)，而从中间插入/删除是 O(n)。为什么会这样？

另外 - 如果我有一个包含 5 个元素的动态数组，并且我在位置 6 插入一个新元素，则操作为 O(n)，而如果我使用该函数附加到数组的末尾，则为 O(1)。假设数组在任何一种情况下都不需要调整大小，这不是相同的操作吗？或者附加到动态数组是否真的在位置 6 之外的某个地方插入了新元素？

谢谢！

编辑：我认为我的主要困惑是在数组末尾插入和在相当于数组末尾的特定位置插入之间的区别。

我想指向数组末尾的内存地址的指针很方便，这就是附加操作很快的原因。相反，如果我指定一个精确的位置（即使它是数组的末尾），它不会知道在那个位置插入就等于使用上述内存地址，所以它必须遍历整个数组，是吗？