当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; 
    } 
}

我只需要找到渐近界限，但我不能这样做，直到我想出多少次循环实际运行。我猜的是另一个涉及平方根的求和，但我不确定如何开始。

这听起来像作业，所以你得到的只是一个提示：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）在每个迭代操作是恒定的。）

啊，非常感谢。这绝对是一个有趣的运行时间。另外，数字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）。

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

相关推荐