以下是什么时间复杂度？

Question

以下函数的时间复杂度是多少？

内循环的时间复杂度如何为log（n）？ 给出内循环执行n/i次的每个i.its运行时间是n *Σ（从i = 1到n）{n/i} ..并且我没有得到它

fucntion(n) 
{ 
    for(int i=1;i<=n;i++) 
    { 
    for(int j=1;j<=n;j+=i) 
    { 
     printf("*"); 
    } 
    } 
} 

Answer 1

在内循环的第一次运行中，我们将循环n次。在第二时间，我们将跳过所有其他数，所以我们循环Ñ/2倍，然后Ñ/3倍等。这继续直到最终循环去哪里Ñ/Ñ = 1穿过循环。

如讨论的here,1 + 1/2 + 1/3 + ... + 1/n是O（log n）。由于我们正在做n次，所导致的复杂性是O（n log n）。