大家好
这是我写的 糟糟的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
谢谢