[問題] 時間複雜度

作者: keke0421 (zrae)   2012-10-16 08:16:32
大家好
這是我寫的 糟糟的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
謝謝
作者: FRAXIS (喔喔)   0000-00-00 00:00:00
這樣你遞迴根本沒把問題縮小,不就無窮遞迴下去了..

Links booklink

Contact Us: admin [ a t ] ucptt.com