问题标签 [asymptotic-complexity]

让我们以二分搜索为例，最好的情况下运行时间将在第一次比较中获得

key_to_find == (imin + imax) / 2;

最佳案例运行时间将由 O(1) 表示。我完全理解这一点，但让我感到困惑的是为什么使用 O(1) 以及为什么我不能使用 Θ(1) 或任何其他表示法。

IE 。如何确定我应该使用哪种表示法来表示运行时间（最佳、平均或最坏情况）。

你能告诉我这段代码的渐近复杂度吗？

我想到了两种解决方案。

一种）

并解决重复问题：

b) 但是我不太确定最后两个语句的复杂性，因为如果 n 大于 950，算法将调用 f(i)，直到 i 小于 950，然后继续调用 f(n-2)。所以，另一种解决方案是这个：

并解决重复问题：

我实际上认为第二个是正确的，但我不确定。谢谢你的帮助。

如果一个算法需要C(n+r-1, r-1)个步骤来解决一个问题，其中n是输入的个数，r是一个常数，算法的步骤是否考虑指数增长？</p>

我对算法很陌生，我有一些问题。假设我有一个排序算法，它以 O(n^2) 对数据进行排序，运行时间复杂度很高。例如，这可能是选择排序。现在，假设我没有使用选择排序，而是使用 HashTable，它将运行时间减少到 O(n)。

• 额外的空间复杂度对运行时间分析有影响吗？
• 在陈述答案时，我如何定义这两者之间的关系？
• 还是它们完全不同？

任何帮助，将不胜感激。

这是我试图分析的算法（见下文）。我不明白为什么 O(n)当合并排序具有时间复杂度时O(n logn)，它们似乎都在做同样的事情。

那么两者都具有相同的 j 时间复杂度，如果您将 j 保留为行，则2^j X c(n/2^j)=cn并且它们的运行时间均为log n，其中 n 是元素的数量。

谢谢，丹尼尔

在 n 元素数组中排序处理需要；
在 X 算法中：10 ^-8 n ²秒，
在 Y 算法中 10 ^-6 n log ₂ n 秒，
在 Z 算法中 10 ^-5秒。

我的问题是如何比较它们。例如对于 y 根据 x 工作得更快，我应该选择哪个元素的数量？

我试图证明 Quicksort 算法的以下最坏情况，但遇到了一些麻烦。最初，我们有一个大小为 n 的数组，其中 n = ij。这个想法是，在快速排序的每个分区步骤中，您最终都会得到两个子数组，其中一个大小为 i，另一个大小为 i(j-1)。在这种情况下，i 是一个大于 0 的整数常数。我已经绘制了一些示例的递归树，并理解为什么这是最坏的情况，并且运行时间将是 theta(n^2)。为了证明这一点，我使用了迭代方法来求解递推方程：

所以看起来复发是：

在这一点上，我有点不知道该怎么做。看起来如果展开，最后的总和将导致 j^2，但我需要证明它以某种方式等于 n^2。任何有关如何继续此操作的解释将不胜感激。

我想知道这个函数的计算复杂度是多少？

2^(log(n)-1)

日志以 2 为底。

在 Big Theta 表示法中，每个 ? 值的常数c1和不同。c2n

定义：

我有以下问题。给定一个包含 n 个元素的集合 S，我需要生成所有可能的重复组合，而不考虑大小 k=1,2,...,m 的顺序。

例子：

所有可能的组合是：

显然，步骤 k 的组合可以使用在 k-1 处获得的组合来计算。什么是获得所有 k 的所有组合的最佳算法（伪代码）及其复杂性。