问题标签 [asymptotic-complexity]

为明天的期中考试而学习，而这些时间复杂性让我很挣扎。我将回顾书中的简单示例，并针对此示例

交换排序

对于这种 Exchange 排序的“每个案例时间复杂度”，我理解我们几乎分析jfor 循环的部分，因为它具有基本操作（交换）。因此，如果您列出通行证总数，则由下式给出：

现在我的问题是...... 1 来自哪里？我以为是n-1 + n-2 +... + n。

此外，我真正不明白的是如何提出(n-1)n/2.
这显然是我在中期必须想出的，通过观察，(n-1)n/2并不直观......我知道如何想出T(n) = (n-1) + (n-2)等等，我想......

有人可以用外行的话向我解释一下，这样我明天的期中考试就可以想出这样的答案吗？

有人知道具有非单调最坏情况行为的自然程序或算法吗？

通过非单调最坏情况行为，我的意思是存在一个自然数 n，使得大小为 n+1 的输入的最坏情况运行时间小于大小为 n 的输入的最坏情况运行时间。

当然，很容易构建具有这种行为的程序。自然程序中的小 n（如 n = 1）甚至可能发生这种情况。但我对大 n 非单调的有用算法感兴趣。

最近，我正在尝试解决 CLRS 中的所有练习。但有一些我无法弄清楚。这是其中之一，来自 CLRS 练习 12.4-2：

描述在 n 个节点上的二叉搜索树，使得树中节点的平均深度为 Θ(lg n)，但树的高度为 ω(lg n)。给出一个 n 节点二叉搜索树高度的渐近上限，其中节点的平均深度为 Θ(lg n)。

任何人都可以分享一些想法或参考来解决这个问题吗？谢谢。

使用合并排序算法将长度为 n 的 n 个字符串列表按字典顺序排序。此计算的最坏情况运行时间是？

我把这个问题作为家庭作业。我知道在 O(nlogn) 时间内进行归并排序。对于长度 in 的字典顺序是 n 次 nlogn 吗？还是 n^2 ？

因此，在列表中找到最大元素需要 O(n) 时间复杂度（如果列表有 n 个元素）。我试图实现一种看起来更快的算法。

这真的更快吗？！你会说渐近时间复杂度是什么（紧界）？

我正在尝试自学计划，而我最苦恼的概念是空间和时间复杂性。我正在做本章末尾的一些练习，但我无法弄清楚以下两个。我试图找出每个函数的渐近时间复杂度（紧界）。

为此，我认为渐近时间复杂度为 O(n)，因为除非满足停止条件，否则我们每次都调用一次迭代函数。

第二个函数由下式给出：

在我看来，这是 O(n^2)。很难解释我为什么这么认为，所以我只是在观察它。

这是MIT OpenCourse Introduction to Algorithm作业中关于Asymptotic Notation的问题：对于以下每个陈述，确定对于渐近非负函数f和g 是否始终为真、从不为真或有时为真。如果它总是正确或从不正确，请解释原因。如果它有时是真的，请举一个例子说明它是真的，一个例子说明它是假的。

我认为这从来都不是真的。这是我的证明：

结果与 相矛盾g(n) ≠ O(f(n)) (Big-O note)。同样地，

与 相矛盾f(n) ≠ O(g(n)) (Big-O note)。

解决方案说有时是真的：

我的证明哪里做错了？另外，我无法理解解决方案。对我来说||n*sin(n)||看起来像矢量规范。

考虑一个最初为空的 RB-tree，我们将 m 个元素插入其中。插入一个元素需要 O(log n) 时间，其中 n 是当前插入的元素数。所以我可以写出 m 次插入的总时间，如： sum log(i) for i=1..m == log(Pochhammer(1,m) ；由 WolframAlpha 提供。

事实上，m*logm 和 log(Pochhammer(1,m) 的比率收敛到 1，所以我想这就是为什么我以前没有见过 log--Pochhammer 的原因。

计算机科学中还使用了哪些其他“奇异”功能？我知道 inverse-ackerman 出现在 Union-Find 等...

我正在通过“计算机算法基础”一书寻找多阶段图问题。

它说：

作者说复杂度是 O(|V| + |E|)。|V| 是顶点数，|E| 是边数。

我知道 for 循环针对顶点总数运行，并且内线必须选择一个近边。

我无法理解背后的逻辑

请注意，我在这里要求 little-o（请参阅此处的类似问题）-对于 big-o，这显然是错误的-对于 little-o，感觉正确但似乎无法证明...

编辑：很高兴我提出了辩论:) 为简单起见假设 f,g > 0