解釋爲什麼這個非簡化的複雜表達式是這樣的？

我試圖從我的教授的講義中瞭解複雜類算法，但我仍然無法得到它的一個竅門。解釋爲什麼這個非簡化的複雜表達式是這樣的？

void sort(int a[], int N) { //N is the length of the array 
    for (int base=0; base<N; ++base) 
     for (int check=base+1; check<N; ++check) 
     if (a[base] > a[check]) 
      std::swap(a[base], a[check]); 
}

在他的筆記上他說這個表達式是8N^2 + 12N + 6。

從我完全理解的複雜等級來看，這是N^2，因爲它是其餘增長最快的。我們忽略常量，因爲它們在無限時無關緊要。

但是，我想知道他是如何得到這些常量的。

我不明白他是怎麼得到的+6。當這個函數被調用一次時，究竟只運行總共6次？我看到int base = 0僅創建一次，因爲它屬於外部for-loop。

編輯：所以我發現+6只是這個函數需要運行的最低限度。在for循環只執行一次的情況下...所以總行數？那麼我們做一個[]和int N的副本，然後我們有我們的for循環和if語句。一切都增加到6.

怎麼樣的12N？

來源

2016-01-29 Jacob Macallan

是不是隻是bubblesort？我不知道這個應該和其他的東西有什麼關係（爲什麼你需要int N？你知道這個信息已經是類似於a.Length的東西了） –

這裏唯一正確的是* n *複雜性。常量全部組成。 6是什麼意思？ 6什麼？在什麼平臺上？由於常量是組成的，你可以彌補內循環每次迭代運行12次或任何東西。我必須說，這是一種愚蠢的行爲。 –

只有在假設此算法中的基本元素執行一些時間時，纔可以獲得這些常量。我們不知道你的教授如何定義這些。不過正如@AmiTavory已經指出的那樣，這在實踐中是無關緊要的。 – Henry

As Ami Tavory建議這看起來像廢話。更仔細看後，它仍然是非常怪異的表達是非常混合不同的操作週期，因爲這將是原子的...如果我忽略了相關我認爲是這樣的：

void sort(int a[], int N) {     // ?T 
    for (int base=0; base<N; ++base)   // 1 +(3+2)N 
     for (int check=base+1; check<N; ++check) // 2N+(3+2)M 
     if (a[base] > a[check])    // (2+1+2)M 
      std::swap(a[base], a[check]);  // (2+2+2)M 
}

當我做野假設關於存儲器/寄存器/直接存取或ALU操作有多少個週期。 M = ~ (N^2)/2（抱歉懶得從系列總和中得到實際的計數）是內部循環迭代的次數。所以，當我總結所有我得到：

16*(N^2)/2+7N+1+? 
8*N^2 + 7N + 1+?

這是非常接近你的表情。由於我使用了不準確的M，並且不知道背後的架構，所以結果可能會有所改變，可能有利於您的表達。所以函數init和return被認爲是~5個週期。如果我連懷爾德則認爲：

int a[]; // 2 // heap -> reg 
int N; // 2 // heap -> reg 
{}  // 1 // stack return (I would guess it should be also 2)

，所以我就：

8*N^2 + 7N + 6

對你：

8*N^2 + 12N + 6

爲了使這個準確的，你應該：

計算M恰好
獲得操作的定時的結構，這是用於
斷裂代碼原子操作

區分直接/存儲器（堆/堆棧）/寄存器訪問（可能甚至讀/寫），ALU操作更多...例如，如果swap(a,b) { c=a; a=b; b=c; }它不是由異或荷蘭國際集團完成了...現在像我想你可以指望週期...

例如，看看這裏Machine cycle timings for Z80在哪裏是我的Zilog Z80A完整指令集與機器週期時序的鏈接。所以你可以看到每種類型的指令真的是不同的。你應該爲你正在學習這些東西的平臺/架構有類似的東西。

來源

2016-01-30 09:52:52 Spektre

非常感謝您的回覆。我給你的情景是在他的講義中，無論我多次閱讀，我都無法理解它。知道這是非常糟糕的是安慰。我至少知道我現在理解複雜課。 –

解釋爲什麼這個非簡化的複雜表達式是這樣的？

回答

相關問題