[問題] 時間複雜度
看板Prob_Solve (計算數學 Problem Solving)作者keke0421 (zrae)時間12年前 (2012/10/16 08:16)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/3 (看更多)
大家好
這是我寫的 糟糟的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
推
10/16 20:17, , 1F
10/16 20:17, 1F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
