推 FRAXIS:這樣你遞迴根本沒把問題縮小，不就無窮遞迴下去了.. 10/16 20:17
大家好
這是我寫的 糟糟的code
http://codepad.org/pnM8F8He#line-23
我想分析這個code的時間複雜度
我的想法是
當input第一列資料的的時候 , ex:23 43 12 34 56
也就是main()裡面第一個for送資料進make_new_array函示
有三個fun
有關make_new_array這個function:
這個function 本身會呼叫is_sol , is_soll 兩個 recursion function
而每一個recursion function 我自己判斷應該是T(n) 所以兩個是2*T(n)
而本身這個function還會有swap，若n個數，最差的情況會swap n-1次 所以
總共這個function的時間複雜度是 T(n) = 2T(n) + Θ(n)
但這只是一個input data
若有n個input data 所以總共的時間複雜度是T(n) = 2*T(n^2) + Θ(n^2) = Θ(n^2)嗎?
不好意思 第一次自己判斷自己寫的code的時間複雜度
不太確定 所以特問各位大大QQ
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.37.163.189