问题标签 [asymptotic-complexity]

我使用分治技术实现了一个为数字 (a^n) 供电的程序。我实现了相同问题的两个版本：

版本 1：

版本 2：

版本 3：

Q1：以上哪个版本的复杂度是θ(lg n)？

Q2：如果版本 2 的复杂度为θ(lg n)，为什么？因为虽然第 2 版中的问题大小是除以 2，但子问题的数量也是 2，所以我觉得第 2 版会按θ(nlg n).

我不确定我的结论。

谢谢

检测一条线是否与凸多边形相交的 O(n) 算法包括检查多边形的任何边缘是否与该线相交，并查看相交的数量是奇数还是偶数。

是否有渐近更快的算法，例如 O(log n) 算法？

递归关系

T( n ) = 2T( n /2) + n lg lg n

（其中 lg 是以 2 为底的对数）可以使用主定理解决，但我不太确定答案。我找到了我的答案，但为了防止信息级联，我没有在这里提及。请帮我找到上面的大 O 和 Ω。

我们刚开始在课堂上学习big-o。我理解如果存在两个常数 c,k 使得对于所有 x>k |f(x)|<=c|g(x)|，f(x) 是 g(x) 的 big-o 的一般概念。我有一个问题，是否需要我们包含 <= 来签名，或者放置 < 符号是否就足够了？

例如：假设 f(x)=17x+11，我们要证明这是 O(x^2)。那么如果我们取 c=28 和 x>k=1，我们知道 17x+11<=28x^2。因此，由于我们知道 x 将始终大于 1，这意味着 28x^2 将始终大于 17x+11。那么，我们真的需要包含等号 (<=) 还是只写 (<) 就可以了？

提前致谢。

An algorith with size n=100 takes 21 seconds to run. With size n=1000 it takes 31 seconds and with n=10000 takes 41 seconds to run. What is the running complexity?

If I try O(n) Then: T(n)=(21*1000)/100 = 210 s (Not O(n))
If I try O(n^2) Then: T(n)=(21*1000^2)/100^2 = 2100 s (Not O(n^2))
If I try O(log n) then: T(n)=(21*log1000)/log100=31.5 (Not O(log n))

The other option I am given is O(1/n). How do I calculate this?

我有一个一直困扰我的家庭作业问题。它要求您证明函数 Sum[log(i)*i^3, {i, n}) （即 log(i)*i^3 从 i=1 到 n 的总和）是 big-theta (log(n)*n^4)。

我知道 Sum[i^3, {i, n}] 是 ( (n(n+1))/2 )^2 并且 Sum[log(i), {i, n}) 是 log(n! )，但我不确定 1) 我是否可以将这两者分开处理，因为它们是总和中同一产品的一部分，以及 2) 如何开始将其转化为有助于我证明的形式。

任何帮助将非常感激。谢谢！

最近我在链表上遇到了一个有趣的问题。给出了排序的单链表，我们必须从这个列表中搜索一个元素。

时间复杂度不应超过O(log n). 这似乎我们需要在这个链表上应用二分查找。如何？由于链表不提供随机访问，如果我们尝试应用二进制搜索算法，它将达到 O(n)，因为我们需要找到链表的长度并走到中间。

有任何想法吗？

如何解决这种重复：T(n) = T(n/2) + T(n/4) + O(1)

Master Method 似乎没有帮助，因为这不是T(n) = aT(n/b) + f(n). 我被困了很长一段时间。

在T(n) = 2T(n/2) + M(n)中，T前面的2从何而来。n/2 因为它是除法，而 M(n) 是线性的，但我不知道 2 是干什么用的？

有一个我正在尝试解决的问题，非常感谢一些帮助！时间复杂度是多少...

外部 for 循环运行 n 次。我不确定如何k+= log n在内部循环中处理。我的想法是它是O（n ^ 2）。将 log(n) 添加到 k 并不能获得额外的 n 个循环，但我认为它小于 O(n*log n) 。显然，这只是一个猜测，任何帮助弄清楚如何在数学上证明这一点将不胜感激！