问题标签 [asymptotic-complexity]

我有一组问题，我得到一个 f(n) 和 g(n)，我应该确定 f(n) 在哪里是 O(g(n))、Ω(g(n)) 或 Θ( g(n))

而且我还必须确定正确关系的 c(s) 和 n0。

我该如何着手解决这样的问题？

这是我遇到的问题的一个例子

f(n)= lg(n^2) g(n)=n lg(n)

在解决重复问题时，我遇到了忽略地板和天花板的地方。

来自CLRS （第 4 章，第 83 页）的示例，其中忽略了地板：

这里（第 2 页，练习 4.1-1）是一个忽略上限的示例：（ 编辑：我从公众舆论中得知这有点可疑。）

事实上，在CLRS ( pg.88 ) 中提到：

“解决重复问题时，地板和天花板通常无关紧要”

我的问题：

1. 这里的“通常”是指所有情况吗？如果是的话，我可以一直忘记它们。
2. 如果不是，那么在解决重复问题时，地板和天花板何时真正重要？

注意：这不是作业问题。我在刷新我的 DS 和算法概念时想到了它。

我正在尝试和朋友一起做作业，一个问题询问线性探测方法的搜索、添加和删除的平均运行时间。我认为它是 O(n)，因为它必须检查一定数量的节点，直到找到要添加的开放节点。并且在搜索时，它从原始索引开始并向上移动，直到找到所需的数字。但我的朋友说它是 O(1)。哪一个是对的？

我刚刚开始了关于渐近分析的课程，在我们的一个作业中，我应该在不改变复杂性的情况下向函数添加功能。复杂度为 log(N)。作业指南特别要求我将运行时更改为“常量”。将其设为 3Log(N) 是否会考虑将其更改为常数？

我在解决大 theta 表示法时遇到问题。我知道大 O 表示法表示最坏情况和上限，而 Omega 表示法表示最佳情况和下限。

如果给我一个在 O(nlogn) 时间和 Omega(n) 中运行的算法，我将如何推断 Theta 等于什么？我开始假设当且仅当 O 和 Omega 相等时才存在 theta 符号，这是真的吗？

考虑函数 F：2^(3*n) + n^2

函数 A: 2^(3*n) 可以用作 Big Theta、Omega 或 O 作为 F 的表征吗？为什么？

我正在修改 Big Omega、Big Theta 和 Big O 的概念，我遇到了这个例子，但不知道从哪里开始。

我和我的朋友发现了这个问题，我们无法弄清楚如何解决它。它不是微不足道的，标准的替换方法并没有真正起作用（或者我们不能正确应用它）这应该是快速排序与等级问题的枢轴。

以下是重现：

T(n) = T(n^(1/2)) + T(nn^(1/2)) + n

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

在以下 2 个案例中，我对时间和空间复杂度有疑问

块引用

案例一：

递归：阶乘计算。

这里时间复杂度如何变成 2*n 和空间复杂度与 n 成正比。

和

案例二：

迭代：-

时间复杂度与 n 成正比，空间复杂度是常数。这总是让我感到困惑。

我在我的书以及互联网上的几个网站上搜索了高低，但我并不完全确定我的答案。

关于存在的反转数量，我需要给出 InsertionSort 和 FingerTreeSort（基于 RB-Trees）的渐近运行时。InsertionSort 运行时间为 O(n+INV)，FingerTreeSort 运行时间为 O(n+n*lg(INV/n+1)。我需要给出 INV = 0、n、n^1.5 和 n^2/ 的渐近运行时4.

我自己想出的是 InsertionSort 运行在：O(n)、O(n)、O(n^2) 和 O(n^2)

这个对吗？为什么不？（我特别不确定 INV = n 和 n^1.5）

对于 FingerTreeSort：O(n*lg(n))、O(n*lg(n))、O(n*lg(sqrt(n))) 和 O(n*lg(n^2))

我对 FingerTreeSort 中的所有内容都存有疑问，但我认为它们应该是这样的。如何找到正确的渐近运行时？例如对于 FingerTreeSort 和 n^1.5，我认为它会通过插入通用运行时给出 O(n+n*lg(n^1.5/n+1) 并简化： O(n+n*lg (sqrt(n)+1) 并且看到它是渐近的，我可以忽略 +1 和 +n 等较低的数字给我 O(n*lg(sqrt(n)))。这是正确的做法吗?

提前感谢那些回答这个问题的人。我非常喜欢它:)

附言。用java编写，这对问题并不重要。

假设我有这个功能：（Haskell 语法）

该函数执行的工作（计算量）是多少？

起初我以为它显然是恒定的，但如果类型x不是有限的，意思是 x 可以占用任意数量的内存呢？人们还必须考虑通过复制完成的工作x，对吗？

这使我相信该函数所做的工作实际上与输入的大小呈线性关系。

这本身不是家庭作业，而是在我必须定义该函数完成的工作时提出的：

我相信这也有类似的问题。