[理工] [資結] Time complexity

[dunkjames (Firefighter)]

for i=1 to n do
{
 x=n;
 while (x>0) do
  x=x-i;
}

求 x=x-i大約作幾次?

解答是nlogn次

why?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 42.72.135.68
推 wyrj:第一次while會做n次 第二次做n/2 第三次做n/3 ...第n次做1次
→ wyrj:n(1+1/2+1/3+...+1/n) = O(nlogn)
推 louis719:樓上神!!!
→ dunkjames:喔喔 我懂了 3Q