algorithm - 算法中的时间复杂度。选择Big-O和omega

Question

所以我有这个作业，我们应该在其中查看以下算法:

 Input: An array A storing n elements
 Output: An array B, where B[i] = A[0] + A[1] + ... + A[i].

    for i = 0 to n-1
    Add the numbers A[0] thru A[i].
     Store the result in B[i].

之后，我们应该首先以 O(f(n)) 的形式说明算法的时间复杂度。之后我们应该证明时间复杂度也是 Ω(f(n))。

现在我已经完成了第一部分并说因为 T(n) = n(n-1)/2 我们可以声明 T(n) = O(n^2)。

我遇到的问题是作业的第二部分。怎么算法也是Ω(n^2)？从这些符号的定义来看没有任何意义。如果 Ω(n^2) 那么这意味着 T(n) = n(n-1)/2 比 f(n) = n^2 增长得更快。这不可能是真的。

我知道当我们达到大量 n 时，T(n) 由 n^2 的平方项支配。但是 f(n) = n^2 仍然不是 T(n) 的下界，对吗？那怎么可能是Ω(n^2)呢？

如果我的英语不好，我很抱歉，但我希望你能理解我的问题并能帮助我。我真的很困惑。

Answer 1

The problem I have is with the second part of the assignment. How can the algorithm also be Ω(n^2) ?? It doesn't make any sense from the definitions of those notations.. If Ω(n^2) then that implies that T(n) = n(n-1)/2 grows faster that f(n) = n^2. And that can't be true..

请记住，Big-O 和 Big-Omega 的定义都涉及常量。

为了证明它在 Ω(n²) 中，您需要一个常量 c，使得 n(n-1)/2 ≥ cn² 足够大n(即所有 n 都高于某个值)。您的观察只是表明所述常量不能为 1。