问题标签 [time-complexity]

我在 Haskell 中玩弄这个代码 kata，我遇到了这个主题中的问题。

找到索引为单个数值的数组的中点很简单，但 Haskell 的数组索引可以是 Ix 类型类的任何实例，包括例如元组 (Int, Word, Card)，其中 card 是Ix 但不是 Num。

获取数组中点的一种方法是查询其长度，查询索引列表，然后删除该列表的一半，但这需要 O(n) 时间。

有谁知道一种在恒定时间内索引的方法？我觉得应该有一个，因为 Ix 范围应该与整数范围双射。

上周我在学校有一个任务，要实现一个计算斐波那契数列中第 n 个数的函数。“子任务”是使用累积（可能不是正确的翻译）来实现它，以便给函数 O(n) 时间复杂度。在我尝试制作函数（Int -> Integer）之前，这一切都很好。通过一些实验，我意识到对于非常大的数字，时间复杂度接近 O(n^2)。我突然想到这一定是因为 Integer 的实现，这让我有点好奇它是如何工作的。我做了一些谷歌搜索，没有找到任何似乎有用的东西，所以我转向你们，希望得到一个解释或一个彻底解释它的链接。

我的代码：

我感谢所有的答案

维克多

这两种算法是否具有相同的 Θ(n^2) θ 表征？

如果不是，那么这是否意味着这种表征不是 Θ(n^3)？

如果一个函数 A 调用 n^c 个函数 B 并且在 O(n^2) 时间内运行，那么函数 A 的时间复杂度是多少？它只是多项式 (n^c) 以及 c 刚刚变大吗？

我被要求找到复杂度类，但我不确定我应该使用 Big-Omega 表示法还是 Big-O？但我假设它是 O(N/2)，然后是 O(N)，如果我放弃常数。

对于这个我相信它是 O(N) * O(N+1) -> O(N^2 + N) 然后在我放弃 N 之后是 O(N^2)？

在第一个中，我对 n、logn 等使用替换方法；都给了我错误的答案。
递归树：我不知道我是否可以申请，因为根将是一个常数。

有人可以帮忙吗？

这是G. Michael Scneider 和 Judith L. Gersting的教科书Invitation to Computer Science的直接引述。

在第 3.4.2 节的末尾，我们讨论了在未排序列表上使用顺序搜索与排序列表然后使用二分搜索之间的权衡。如果列表大小为 n=100,000，则在第二个备选方案在比较次数方面更好之前，必须进行多少次最坏情况搜索？

我真的不明白这个问题在问什么。

顺序搜索是有序的（n），二进制是有序的（lgn），在任何情况下lgn总是小于n。在这种情况下，n 已经给出，所以我应该找到什么。

这是我的家庭作业之一，但我真的不知道该怎么做。谁能用简单的英语为我解释这个问题？

我很难确定欧几里得最大公分母算法的时间复杂度是多少。这个算法的伪代码是：

它似乎取决于a和b。我的想法是时间复杂度是 O(a % b)。那是对的吗？有没有更好的写法？

是否可以通过保留一个计数器来查看算法经历了多少次迭代，或者是否需要记录持续时间？

我一直在自学Big-O。我了解如何为算法提供以下符号的示例：

上）：

O(N^2):

O(N^3):

我遇到了这些我不太理解的符号。我如何在算法方面给出这些例子？

也许我应该这样说：编写一个算法，它的运行时间与以下成正比：

1. O((n^3)/4)
2. 记录 n^3
3. O((log^2)n)+O(n)
4. 4^n
5. n^3/2