當n> 0時，n可以多少次floor（sqrt（n）） - 1？

假設我們有一個函數

void foo(int n){ 
    int i = n; 
    while(i > 0){ 
    //do an O(n) operation 
    //do some O(1) operations 
    i = sqrt(i) - 1; 
    } 
}

我只需要找到漸近界限，但我不能這樣做，直到我想出多少次循環實際運行。我猜的是另一個涉及平方根的求和，但我不確定如何開始。

來源

2012-02-15 KylePDM

這聽起來像作業，所以你得到的只是一個提示：let m = log n。 – 2012-02-15 06:08:56

這個問題沒有被分配，它是在一個練習期中的一個問題上被標記爲「比你要測試的更難」。但我會把它標記爲家庭作業：3 – KylePDM 2012-02-15 06:10:36

你想找到你循環執行的次數。

如果我是< 2，那麼循環最多執行兩次。

因此，如果我< 4循環將執行最多3次。

因此，如果我< 16循環將執行最多4次。

因此，如果我< 256循環將執行最多5次。

...

等

你看，如果我< 2 ^（2^M），那麼循環將最多（M + 2）倍執行。

這意味着，有時它會執行次數的順序是log（對數（N）），

因爲我開始以n。

因此整體的複雜性是O(n*log(log(n))。

（這就是如果O數（1）在每個迭代操作是恆定的。）

來源

2012-02-15 06:06:29

啊，非常感謝。這絕對是一個有趣的運行時間。另外，數字O（1）操作如何改變整體的複雜性？ – KylePDM 2012-02-15 06:29:22

@Kyle如果「做一些O（1）操作」中的「某些」取決於「n」，那麼單行代表的成本就不能再被忽略了。如果說，「一些」實際上是「O（n^3）」，那麼這個成本將推到循環。 – AakashM 2012-02-15 09:22:02

同爲O（n日誌log n）的作爲斯托但這裏有一些更清晰的邊界。若i =地板（SQRT（i））的-1，

如果n < 1，它循環零時間
如果n <2²，它循環至多1時間
如果n <（2 2 1）² = 5 2時，它至多循環2次
如果n <（5 2 +1）2 = 26 2，它最多循環3次
如果n <（26 2 +1）2 = 677 2，它至多循環4次

根據On-Line Encyclopedia of Integer Sequences，該序列（1,2,5,26,677，...）漸近於1.22 ^（2^k）[並且第k個數字表示數字o f高度至多爲k的二叉樹]。因此，對於數字n，循環數爲O（log log n），算法爲O（n log log n）。

來源

2012-02-15 07:01:36

當n> 0時，n可以多少次floor（sqrt（n）） - 1？

回答

相關問題