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

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 2/4 = 1：错误是从n / 2而不是n / 2 + 1开始。） 选择n / 2（+1）作为求和的下限只是使得总和很方便地使每个求和等于n / 2。

Answer 3

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

这样做是为了最终简化表达并找到特定的下限。