close
早上六點多了,我竟然還是沒有睡著,
躺在床上睡不著的時候,就會亂想一些有的沒有的,
其他想的就不談了,主要是在想論文中
學長寫的algorithm的time complexity的合理化,
而藉此來寫其他三個algo.的寫法,
但想到一半就覺得有點問題,
現在起床後下來看了一下,似乎分析的有點隨便,
雖然還算是合理,
但實在是太大了,要用到O(n^4).....
而我寫的程式是只有O(n^3)而已,
雖然解釋的方法和實作上有些不同,
但很多東西他都取最大的為主,
以參數來說Rt Rs最大...那iteration就不會有g'-1個
在至少g'-1 iterations中..每個iteration有 O((m+g')^3)
而m及g'會隨著iterations慢慢減少,
以最慢的減少速度來看,最少每一步都會少1...
也就是會隨著 m, m-1,m-2,m-3 減少
那這樣的 recursion 以常數減少的話,
會還是變成 O(g'(m+g')^3) 是這樣嗎?....
慘了...太久沒算這種的....
想一下...等差級數求和的公式是什麼 XD 以常數減少的話是用這個來算,
然後打到一半我才想起來....它被3次方包住,不能這樣算...
在想的途中...好啦...已經搞懂是如此了, (假如是常數減少的話合理)
但...以外面多個3次方來說..每減1的話...我不會算了...>"
全站熱搜