问题标签 [big-theta]

谁能告诉我以下解决方案是否正确？

我正在尝试计算t(n) = t(n-2) + (n-2)²的运行时间

进一步评估

=> t(n)=t(n-4) + (n-2)² + n²

=> t(n)=t(n-6) + (n-6)² + (n-2)² + n²

...因为它减少了 2，所以它大约有 n/2 项，并且通过扩展我们拥有的所有正方形 (n/2) * (n²)，它等于 n³。所以运行时间是theta(n³)

这是正确的解决方案吗？

分析这个算法（伪代码），我可以计算完成所需的步骤数，并用线性算法 Θ(n) 来分析它的效率。好的。

以下代码取决于循环内的内部公式才能完成：

显然它不像第一个那么简单，我不能说循环重复 100 次，因为循环内 A 和 B 的增量不规则。我如何计算这个特定算法的步数以研究它的效率？

我在之前解释这个问题的方式中发现了一个错误，所以再次出现：

分析这个算法（伪代码），我可以计算完成所需的步骤数，并用线性算法 Θ(n) 来分析它的效率。好的。

以下代码依赖于循环内部的内部公式才能完成，交易是代码中没有变量 N，因此该算法的效率将始终相同，因为我们将值 1 分配给A & B 变量：

现在我相信这个算法总是在恒定时间内执行。但是我如何使用代数来找出完成需要多少步骤？

我正在研究书中的渐近符号，我无法理解作者的意思。我知道if f(n) = Θ(n^2) then f(n) = O(n^2)。但是，我从作者的话中了解到，对于插入排序函数算法f(n) = Θ(n)和f(n)=O(n^2).

为什么？大欧米茄或大θ会随着不同的输入而变化吗？

他说：

“然而，对插入排序的最坏情况运行时间的 Θ(n^2) 限制并不意味着对每个输入的插入排序的运行时间有一个 Θ(n^2) 限制。”

然而，大哦符号是不同的。他什么意思？它们之间有什么区别？

我很混乱。我在下面复制粘贴：

由于 O 表示法描述了一个上限，因此当我们使用它来限制算法的最坏情况运行时间时，我们对每个输入的算法运行时间都有一个界限。因此，插入排序的最坏情况运行时间的 O(n^2) 界限也适用于其在每个输入上的运行时间。然而，对插入排序的最坏情况运行时间的 Θ(n^2) 限制并不意味着对每个输入的插入排序的运行时间有一个 Θ(n^2) 限制。例如，当输入已经排序时，插入排序在 Θ(n) 时间内运行。

我在考试中答错了这个问题：命名一个既不是 O(n) 也不是 Omega(n) 的函数。

在尝试通过 youtube 自己学习这些东西之后，我认为这可能是一个正确的答案：

(n ³ (1 + sin n)) 既不是 O(n) 也不是 Omega(n)。

那会准确吗？

有人可以帮我理解这个问题吗？我明天的考试可能会有它，但我在互联网或我的讲座中找不到类似的问题。

这是解决数独（9x9）的代码：

有人可以告诉我用 Big O 或 Big Theta 表示法对这个算法进行分类。我得到了 O(n^3) 但我们可以看到那不是真的！所以，给我一个提示或建议如何开始，我将非常感激。如果你愿意，我也可以用伪代码发布！

谢谢，MB

我被要求计算家庭作业的大 theta，但是这方面的讲座材料有点稀疏。

鉴于循环

我已经制定了一个执行图表

它的内部循环增量器让我失望。它执行 (n+1)/2 次，所以大 theta 必须是 (n log n + log n)/2。

我对么？

该块是：

我需要找到 x=x+1 执行次数的 theta 符号。我创建了一个包含一些示例值的表格，但我不知道如何从那里继续前进。这是我的示例值：

I need a little help on figuring out the Big-Theta running time for this function.

I know how what the run time of this function would be if the for loop wasn't in the function, but the loop is throwing me off a little bit. Any advice?