大O證明與開方和日誌

我無法搞清楚如何證明大O證明與開方和日誌

t(n) = sqrt(31n + 12n log n + 57)

是

O(sqrt(n) log n)

我還沒有過尚未處理平方根在大O符號所以我遇到了很多麻煩！任何幫助非常感謝:)

來源

2011-02-24 deedex11

這是功課嗎？如果是這樣，請添加該標籤。 – 2011-02-24 19:50:45

不做功課！只是練習，所以我不認爲這個標籤是必要的，但謝謝！ – deedex11 2011-02-24 20:39:31

大O符號是關於算法特徵（時間花費的時間，內存使用，處理時間）如何隨問題的大小而增長。

常量因素被丟棄，因爲它們不會影響值的大小。

小項也被丟棄，因爲它們最終沒有效果。

所以你的原方程

sqrt(31n + 12nlogn + 57)

立即簡化爲

sqrt(n log n)

平方根分佈，象其他類型的乘法和除法，所以這可以被straightforwardedly轉換爲：

sqrt(n) sqrt(log n)

由於日誌將乘法轉換爲加法（this所以計算尺工作），這將成爲：

sqrt(n) log (n/2)

同樣，我們拋棄常量，因爲我們感興趣的類的行爲

sqrt(n) log n

和，我們找到了答案。

更新

正如已經正確地指出，

sqrt(n) sqrt(log n)

不會成爲

sqrt(n) log (n/2)

所以我推導的最終是錯誤的。

來源

2011-02-24 19:57:54 Bevan

sqrt（log n）不是log（n/2）。 – 2011-02-24 20:00:18

@克里斯達恩。你是對的。讓我的業務逆轉。經典案例，看看我想要什麼，最終在預定義點。謝謝你的收穫。 – Bevan 2011-02-24 20:06:25

不用擔心。我認爲它是一個* big * O，所以我們不必爲最後一點而努力...... sqrt（log n）明顯小於log n最終:) – 2011-02-24 20:30:32

首先找到sqrt()，這將是12nlogn內最大程度的因素。最大程度的因素使得所有其他因素在大O中無關，因此它變成O(sqrt(12nlogn))。一個不變的因素也是無關緊要的，所以它變成了O(sqrt(nlogn))。那麼我想你可以使這個參數等於O(sqrt(n) * sqrt(logn))或O(sqrt(n) * log(n)^(1/2))，並且消除logn的功率得到O(sqrt(n)logn)。但我不知道最後一步的技術理由是什麼，因爲如果您可以將sqrt(logn)轉換爲logn，爲什麼不能將sqrt(n)轉換爲n？

來源

2011-02-24 19:50:08 mellamokb

提示：考慮擴展sqrt（1 + x）的主要條件爲| x | < 1.

來源

2011-02-24 19:53:34

大O證明與開方和日誌

回答

相關問題