算法設(shè)計動態(tài)規(guī)劃(編輯距離)-資料下載頁
2025-08-05 16:48本頁面
【正文】 fp)。 return 0。}/*輸入：fxpimu xwrs輸出：5*/五、復(fù)雜度分析以下為核心代碼部分：for(i=0。i=n。i++) //從i變到0字符串，i個需要i次(添加) d[i][0]=i。 一重循環(huán)時間復(fù)雜度為T(n) for(i=0。i=m。i++) //從0字符串變到j(luò)，j個需要j次(刪除) d[0][i]=i。 一重循環(huán)時間復(fù)雜度為T(m) for(i=1。i=n。i++) { for(j=1。j=m。j++) { if(a1[i]!=a2[j]) d[i][j]=min(min(d[i][j1],d[i1][j]),d[i1][j1])+1。//加一個，減一個，變一個 else d[i][j]=d[i1][j1]。 } }二重循環(huán)：時間復(fù)雜度為T(n*m)總的時間復(fù)雜度為T(n*m+n+m)=O(n*m)最好時間復(fù)雜度為O(n)；最壞時間復(fù)雜度為O(n2)參考文獻[1] （第3版）.電子工業(yè)出版社,（第8次印刷）P48，P5354，P89[2] 科曼(Cormen .)(第二版).機械工業(yè)出版社，(第9次印刷)P2022076
外語相關(guān)推薦
鄂ICP備17016276號-1