上海大學(xué)acm集訓(xùn)隊培訓(xùn)資料(編輯修改稿)
2025-07-13 22:27 本頁面
【文章內(nèi)容簡介】 ]。 a[i] = a[j]。 a[j] = t。 }}使用該函數(shù)時，應(yīng)將Type替換為C++中的數(shù)據(jù)類型3．性能分析 程序P所用時間定義為T(P), T(P)是編譯時間和運行時間之和。 下面我們計算一下選擇排序運行時所要花費的時間 SelectionSortcosttimes for (int i=1。 i=n。 i++)c1 { int j=1。c2 for (int k=i+1。 k=n。 k++)c3 if (a[k] a[j])c4 j = k。 c5 Type t = a[i]。 a[i] = a[j]。 a[j] = t。c6 }那么該算法運行的時間那么，在最壞的條件下，的值應(yīng)該是所以，算法的運行時間為4．漸進符號定義： [大O]函數(shù)，念做是的大”oh”，當(dāng)且僅當(dāng)存在正常數(shù)和，使得對于所有的，有。例 對于所有有，所以。 對于所有有，所以 對于所有有，所以當(dāng)然對于所有有，所以定義： [Ω]函數(shù)，念做是的”omega”，當(dāng)且僅當(dāng)存在正常數(shù)和，使得對于所有的，有。例 對于所有有，所以。當(dāng)然，但是?，F(xiàn)然無論是O還是Ω，都不能精確的描述一個函數(shù)定義： [Θ]函數(shù)，念做是的”theta”，當(dāng)且僅當(dāng)存在正常數(shù)和，使得對于所有的，有。例 對于有且，所以Θ記號要比O和Ω都要精確。排列生成器Θ(n!)void Perm(Type a[], int k, int n){ if (k==n){ //Output permutation. for (int i1。 in。 i++) couta[i] 。 } else //a[k:n] has more than one permutation. // Generate these recursively. for (int i=k。 i=n。 i++){ Type t=a[k]。 a[k]=a[i]。 a[i]=t。 Perm(a, k+1, n)。 //All permutations of a[k+1:n] t=a[k]。 a[k]=a[i]。 a[i]=t。 }}對于下面的程序10 / 10includeiostreamusing namespace std。void Perm(int a[], int k, int n){if (kn1){int i, t。for (i=k。 in。 i++){t = a[k]。a[k] = a[i]。a[i] = t。Perm(a, k+1, n)。t = a[k]。a[k] = a[i]。a[i] = t。}}else{int i。for (i=0。 in。 i++){couta[i]39。\t39。}coutendl。}}int main(void){int a[3] = {1, 2, 3}。Perm(a, 0, 3)。return 0。}該程序的運行結(jié)果為1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2 那么，該函數(shù)就完成了對一個數(shù)組進行全排列的操作下面，分析該程序，我用圓圈代表每次函數(shù)的調(diào)用每次函數(shù)的調(diào)用都用序號表示12853467910k=0k=1k=21. a: 1 2 3 k: 02. a: 1 2 3 k: 1
試題試卷相關(guān)推薦
鄂ICP備17016276號-1