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））個試驗。