如何證明或反駁這個函數是Ω（n^1.5）？

-6

所以我有這樣的遞歸函數： T（N）= T（的log（n））+ T（N-的log（n））+ N如何證明或反駁這個函數是Ω（n^1.5）？

我試過很多次解決它，但我只是沒有成功。（找到theta）基本上，它足以證明或反駁，如果它是歐米茄的n^1,5（Ω（n^1.5））

幫助將不勝感激，提前致謝！

TL; DR：

給出T（N）= T（的log（n））+ T（N-的log（n））+ N

證明或反駁：T（N ）=Ω（N^1.5）

2017-08-06 Elie

它可能被拒絕投票，因爲您沒有展示過努力來解決問題。 –

我一直在谷歌搜索和stackoverflow的問題2天了。沒有什麼與此類似的。有很多使用常量的例子：T（n）= T（n/4）+ T（3n/4）+ n。但是沒有一個在調用中使用FUNCTIONS。很難分析最終與之有關的函數（log（n-log（n-log（n-log）））（等等） – Elie

看起來更適合cs.SE. –

假設T(n)不會突然成爲在n一些值負，我們可以給一個下界的左手側，如果我們忽略第一項：

我們定義一個新的功能S(n)這樣的：

，馬上就可以看到它有條款（忽略掉接一個等）。因此，如果我們不斷擴大：

在這個階段，因爲我們知道log(n) << n任何一個大型n，我們可以在遞歸調用應用泰勒展開的第三項至S(n)：

我們也可以實事求是地忽略第二項。應用這種近似每S(n)電話：

現在，我們知道：

b顯然可以是1。5;因此：

編輯：一些數值測試，以確認該結果 -

代碼：

uint64_t T(int n) { 
    return n <= 1 ? 0 : T(n - log(n)) + T(log(n)) + (uint64_t)n; 
}

結果：

N   T(N) 
-------------------------- 
2   2 
4   6 
8   18 
16   60 
32   181 
64   578 
128   1911 
256   6331 
512   22011 
1024  79304 
2048  279719 
4096  1016217 
8192  3814210 
16384  13902832 
32768  51540129 
65536  195366441 
131072  732435510 
262144  2744988819 
524288  10457580914 
1048576  39910628826

普羅的N^2/log(N)針對T(N)噸：

的關係是線性的，這意味着

...確認給定的結果。

來源

2017-08-07 09:02:57 meowgoesthedog

非常小的格式說明：'\ text {LHS}'（或'\ mathit'，如果你想要斜體）可以防止間距問題，就像數學模式中的'LHS'被格式化爲一個乘法表達式（給出奇怪的間距在'LH'和'S'之間）。否則，通過內聯圖片在StackOverflow上進行數學運算，這是不方便的。（另一個原因爲什麼這是一個更好的問題cs.SE） –

@JeroenMostert啊謝謝你的提示;這個問題真的引發了我的強迫症。 – meowgoesthedog

@JeroenMostert非常感謝您的幫助！ – Elie

如何證明或反駁這個函數是Ω（n^1.5）？

回答

相關問題