问题标签 [big-theta]

我们的教授和各种材料说 Summation(n) = (n) (n+1) /2，因此是 theta(n^2)。但直观地说，我们只需要一个循环来找到前 n 项的总和！所以，它必须是 theta(n)。我想知道我在这里错过了什么？！

考虑到以下算法，

我认为这是Theta(n^2*log(n))。这是正确的还是 Big Theta 比这更高？

如果给我两个函数并要求我找到两者的渐近复杂度，那是什么意思？是 O() 还是 Big Theta？例如 f1(n)=a^n 和 f2(n)=n^3+n^2

我应该说 f1 是 O(a^n) 而 f2 是 O(n^3) 还是应该使用 big-theta？

我无法理解如何将其变成公式。

我意识到会发生什么，对于每一个 i++，你有 1 级乘法减去 j。

i = 1, 你得到 j = 1, 2, 3, ..., 100

i = 2, 你得到 j = 1, 3, 5, ..., 100

我不确定如何根据 Big-theta 来考虑这一点。

j的总数是N，N/2，N/3，N/4...，N/N（我的结论）

如何最好地尝试将其视为 N 的函数？

对于这种插入排序的分析，如算法介绍中所示：

第 5 行的总和说明了什么？我很困惑tj应该是什么意思。为什么它不只是表明它发生了 n*n 次之类的？

有人可以澄清它在说什么吗？

采用以下插入排序算法：

我知道通过检查它很容易 O(n^2) 。但就证明它是 O(n^2) 而言，我将如何去做呢？我可以将所有操作相加，但n + "sum of j=2 to n"据我所知并不会真正导致 n^2。

我真的不知道如何准确地证明这一点。有人可以尝试清楚地解释我将如何以一种适用于 O(n^3) 算法的方式证明这一点吗？

我的理解是，如果一个算法是O(1)，它也是O(n)，，等等，这使它看起来毫无用处O(n^2)。O(n^3)例如，如果有人问我任何算法的 Big-Oh 符号，我可以直接说O(n^n)而不考虑它（字面意思）并且大部分时间在技术上是正确的。

既然（我的理解是）这是真的，那么这些有用的信息如何？打个比方，如果我问某人他们拥有多少房子，“1 到无穷大”这样的答案并不能提供很多信息。一个有用的答案（这有点像 Big-Theta）是“1”。

根据此页面：

陈述：f(n) + o(f(n)) = theta(f(n)) 似乎是真的。
其中：o = little-O，theta = 大 t​​heta

这对我来说没有直觉意义。我们知道 o(f(n)) 的渐近增长速度比 f(n) 快。那么它怎么可能是大θ所暗示的f（n）的上限？

这是一个反例：

在我看来，先前链接的 stackexchange 答案中的答案是错误的。具体来说，下面的陈述似乎是把小欧与小欧米茄混淆了。

由于 g(n) 是 o(f(n))，我们知道对于每个 ϵ>0，都有一个 nϵ 使得 |g(n)|<ϵ|f(n)| 每当 n≥nϵ

所以这里是第一种方法。这些方法的复杂性是什么？我不确定如何确定它以及为什么它与 find 方法相同

作为一个家庭作业问题，我需要通过数学证明来决定 5 ⁿ是 little-o、Θ 还是 7 ^{n的 little-ω。}然后我需要在取双方的对数后重复这个。

我很难理解我被要求做什么。我最好的猜测是说 A(n) = 5 ⁿ和 B(n) = 7 ⁿ然后使用 l'Hopital 的规则，但我不确定如何继续。我只是在寻找正确的方向。

谢谢！