環路複雜

如果我有下面的循環：環路複雜

for(k = 1; k <= n; ++k){ 
    for(j = 1; j * j <= k; ++j){ 
     //O(1) operations 
    } 
}

我知道外環將迭代n次，內循環將迭代floor(sqrt(k))從外環每k^次迭代。

Therfore，確定時間複雜性，我們有這樣的事情，的

\sum_{k=1}^{n} \floor{\sqrt{k}}

不知道如何着手，並在正方面獲得了封閉形式的時間複雜度總和。

2016-04-07 hello

[谷歌搜索]（http://mathforum.org/library/drmath/view/65309.html）可能會有所幫助。 – anukul

我會說你需要整合sqrt（n）=> n ^（1/2）。結果是n ^（3/2）。忘記地板功能。

2016-04-07 15:10:45 marom

@ciamej你說得對。我糾正了它。 – marom

外循環迭代n次，內循環迭代sqrt(n)次。當一個循環在另一個循環內時，你會增加它們的複雜性。因此它運行在O(n^1.5)

2016-04-07 16:38:11 smttsp

「當一個循環在另一個循環內部時，你會增加它們的複雜性。」 - 它不那麼簡單。 –

@KarolyHorvath：這個怎麼樣：「當一個循環在另一個循環內部並且它們互相排斥時，你會增加它們的複雜性」？ – smttsp

在這種情況下，他們不是。 –

回答