algorithm - 他们是如何找到以下代码的下界的？

Question

procedure stars(n)
     for i = 1, . . . , n do
     print “∗” i many times

问题 - 使用 Ω 表示法，下限星星的运行时间，以表明您的上限实际上是渐近紧的。

解决方案 - 为简单起见，假设 n 是偶数。我们降低了迭代 n/2 到 n 期间打印的星数：

我不明白他们为什么要从 n/2 到 n。我该怎么做这个问题？

Answer 1

因为Omega从哪里开始并不重要！下限只有一件事是它必须小于指定的总和。解决方案只是想为总和找到一个严格的下限，因为总和在Theta(n^2)（总和等于n(n+1)/2）。

Answer 2

请注意，总和不是超过j/2，而是超过n/2。对于每个n/2 ≤ j ≤ n，n/2 ≤ j，因此不等式成立，但可能存在n=2的例外：全和为 3，第二个和为 2（不是2²/4 = 1：错误是从n/2而不是n/2 + 1开始。）
选择n/2 ( +1 ) 作为求和的下限只会使总和方便地变得微不足道，同时让每个被加数等于n/2。

Answer 3

请注意，当您对 from 求和时n/2，n您对元素的求和较少，因此这个等式是正确的。

这样做是为了最终简化表达式并找到一个具体的下限。