证明下面的代码在 Θ(nlogn) 时间内运行

Question

这是一道家庭作业题，我真的需要这道题的帮助，我希望有人能帮我解决这个问题

We have n electric light bulbs, with labels from 1 to n. The light bulbs are all turned OFF initially. Each light bulb has a switch, so that flipping the switch will change its status from ON to OFF, or from OFF to ON. At the i-th round, for i=1,2,....,n we will flip the switches of those light bulbs whose labels are a multiple of i, and we are interested to know which light bulbs will be ON after the n-th round.

We can compute the final status of each light bulb using the following code:
Intialize A[1...n] so that each entry is OFF;
for(round i=1,2,...,n) {
  for (position j=i,2i,3i,...){
    if(j<=n) Flip A[j];
    else break;
  }
}
Show that the obove code runs in O(n^2) time

Show that the above code runs in Θ(nlogn) time.

Design a faster algotithm that can compute the final status in O(n) time.

Answer 1

对于从 1 到 n 的每个 i，内循环在 Θ(n / i) 时间内运行。因此整个运行时间是 Θ(n / 1 + n / 2 + ... + n / n).

现在只剩下利用众所周知的事实1 / 1 + 1 / 2 + ... + 1 / n = Θ(log(n))了。您的问题的第 1 部分和第 2 部分到此结束。

要获得更快的算法，请尝试对一些小 n（例如 n = 100）进行实验。最后点亮的灯泡是什么？你能从结果中猜到什么？最后，你能证明你的猜测吗？

证明下面的代码在 Θ(nlogn) 时间内运行

Show that the code below runs in Θ(nlogn) time

algorithm

time

big-o

analysis