以下算法的最佳情况时间复杂度是多少？

Question

我得到以下函数，其中 g 是在 Θ(n²) 中运行的其他函数。此函数的最佳案例时间复杂度是多少？

void f(int n) {
  if(n % 2 == 0) {
    return;
  } else {
    g(n);
  }
}

显然，如果 n 是偶数，函数运行在常数时间，这让我想说 Θ(1)，但我不认为这是正确的答案，因为我不认为这就是渐近紧界已定义。

我在 SO 上看过很多关于大 theta 符号和最佳案例分析的类似问题，但它们都与长度为 n 输入的数组有关，而不仅仅是一个整数。我认为最佳案例分析在这些情况下是有意义的，因为它取决于数组中的元素。

但是，除了 g 之外，这个问题似乎与“数组中的元素”类似

这让我得出结论，实际最佳情况下的时间复杂度是 Θ(n²)。我的理解正确吗？是 Θ(n²) 还是 Θ(1)？

Answer 1

您似乎对 Θ 符号的用法很困惑。

I don't think that's the correct answer because I don't think that's how an asymptotic tight bound is defined.

Θ 表示法是 渐近紧界 并且可以定义为：

For any two functions f(n) and g(n), we have f(n) = Θ(g(n) if and only if
f(n) = O(g(n)) and f(n) = Ω(g(n)).

O 表示法给出 渐近上限 并且 Ω 表示法给出 渐近下限 .

在您提供的算法中，

 void f(int n) 
 {
     if(n % 2 == 0) return;
     else g(n);
 }

其中 g(n) = Θ(n²).

算法的运行时间属于O(n²)和Ω(1)。 我们不能使用 Θ 符号来描述您算法的运行时间 如果我们是考虑 n.

的所有可能值

然而，如果我们看一下算法的运行时间，当n可以取的唯一值是偶数时，也就是 best case，那么我们可以说在best case中，算法的运行时间同时属于O(1)和Ω(1)。因此，我们可以说算法的 最佳情况复杂度是 Θ(1).

注意区别

The running time of the algorithm is Θ(1). //Wrong in this case

和

The best case running time of the algorithm is Θ(1). //Correct in this case

类似地，如果我们查看算法的运行时间，当n可以取的唯一值是奇数时，我们会发现算法的最坏情况复杂度是Θ(n²).

希望对你有所帮助

Answer 2

我不同意@aksingh 的回答。

从给定的，

其实三个时间没有区别（渐近意义上），因为Θ.

请务必注意，描述这些运行次的函数不必是“单个表达式”。

如果你想获得不依赖奇偶校验的结果，你可以写最好，最坏和普通情况运行次是Ω(1)和O(n²)。

为了说明，该图显示了一些假设的运行次（红点）。在绿色和洋红色中，最好和最坏的情况，奇数 n。蓝色，甚至 n.

现在灰色，最好的案例功能。

What is the best case time complexity of the following algorithm?