iPhone下降测试时间复杂度

Question

我正在处理这个问题。以下是背景信息：

您正在一家拥有n层楼的摩天大楼的公司工作，管理层想知道如果iPhone被抛出非常高的窗户，iPhone会做多好。这个想法是，iPhone在下面的某个特定楼层F中完全不受影响。从F以下的任何楼层掉落时，它们不会破裂;当从F层以上抛出时，它们破裂。

我需要制定一个策略，以确定F楼需要O（kn ^（1/k））试验，其中我有> 3个iPhone。

Answer 1

以n ^（1-i/k）（四舍五入）的倍数递减第i个电话（1 < = i < = k）。 当手机中断时，我们需要使用其余手机搜索n ^（1-i/k）的范围。

因此，对于电话i，它在n ^（1-（i-1）/ k）的范围内以越来越多的n ^（1-i/k）进行搜索。因此，我们每次拨打电话的时间最多为O（n ^（1/k））次。

由于有k个电话，这意味着需要O（kn ^（1/k））个试验。