無法計算函數的增長率

您好，我正在嘗試解決上面圖片中的問題，但我不能。

特別是，我的問題是關於圖像中的C（n），最後我得到了「7logn + n ^（1/3）」。（證人c = 1，k = 7）「和+符號的右側，」n ^（1/3）「， < = n「。

從我的角度來看，+符號之間的雙方都是O（n），因此整個C（n）是O（n）。

但爲什麼答案是Big-theta（n^1/3）？

2017-05-05 Ryu

你正確地做了你的數學運算，並且你非常正確地認爲C（n）在O（n）中，但你爲什麼認爲這意味着它不是Θ（∛n）？ Θ（∛n）是O（n）的一個子集。 – ruakh

只有當log是基數2的對數（然後log（8）= 3，因爲2^3 = 8），這纔是真的。（1/9）=（n^3）（12）（log（n）/ 9）=（8loglog（n））^（1/9）=（n^log（8））^ ^（1/9）= n ^（3 * 1/9）= n ^（1/3）

n ^（1/3）與n的第3根相同。

這是O（n ^（1/3）），而不是爲O（log（n））的，因爲前者長期的增長速度：實現的log（n）/（N的無限正

限制^（1/3））等於0.如果你必須切換表達式得到0，那麼另一個將會增長得更快。例如。 n + log（n）將是O（n），因爲n增長得更快，不會與n * log（n）（它是O（n * log（n））混淆。

2017-05-05 20:52:08 maraca

回答