证明下面的代码在Θ（nlogn）时间运行

-2

这是一个家庭作业的问题，我真的需要在这一个帮助，我希望有人可以帮助我走出这证明下面的代码在Θ（nlogn）时间运行

我们有N个电灯泡，标签从1到n。灯泡最初都是关闭的。每个灯泡都有一个开关，因此翻转开关的状态将从ON改变为OFF，或者从OFF改变为ON。在第i轮，对于i = 1,2，...，n，我们将翻转那些标签为i的倍数的灯泡的开关，并且我们有兴趣知道哪些灯泡将是ON后第n轮轮。
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; 
    } 
} 
表明obove代码运行在O（N^2）时间

显示：

我们可以使用下面的代码计算每个灯泡的最终状态上面的代码运行在Θ（nlogn）时间。

设计一个更快的算法，可以计算O（n）时间的最终状态。

来源

2016-02-12 angad singh

你到现在为止尝试过什么？你对这些问题有什么想法.. – Haris

你有什么问题吗？为了表明它运行在O（n^2）中，正如你问题的标题所示？如果你记得那是一个超越的话，那应该很容易。 –

@Haris嗯，我确实尝试计算时间函数，但找不到这样做的方法。我知道如果我可以计算一个时间函数，我可以用Induction来证明这些事情。 –

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

现在只剩下使用众所周知的事实1/1 + 1/2 + ... + 1/n = Θ(log(n))。这完成了你的问题的第1部分和第2部分。

对于更快的算法，尝试做一些小的n（例如n = 100）的实验。最后打开的灯泡是什么？你能从结果中猜出什么？最后，你能证明你的猜测吗？

来源

2016-02-12 16:57:49 WhatsUp

感谢您的解决方案。你能给我一个关于1/1 + 1/2 + ... + 1/n =Θ（log（n））证明的链接。我似乎无法在任何地方找到证据。 –

我GOOGLE了，发现这个：http://math.stackexchange.com/questions/156326/showing-inequality-for-harmonic-series – WhatsUp

证明下面的代码在Θ（nlogn）时间运行

回答

相关问题