比較兩種算法的複雜性：確定適用於兩種算法的基本操作？

Question

對於一項任務，我必須從理論上分析兩種算法（排序）的複雜性來比較它們。然後，我會實施它們，並試圖通過實證確認效率。因此，我分析了兩種算法，並且我知道效率類，但是我在識別基本操作時遇到了問題。有一個提示是我們在選擇基本操作時應該小心，因爲它應該適用於這兩種算法。我的問題是，我不知道爲什麼我應該對這兩種算法採取相同的基本操作。

僞

Algo1：

//sorts given array A[0..n-1] 
for i=0 to n-2 
    min <- i 
    for j <- i+1 to n-1 
    if A[j] < A[min] min <- j 
    swap A[i] and A[min] 

效率：西塔（N^2）

ALGO2：

//sorts given array with limited range (u,l) 
for j = 0 to u-l D[j] = 0 
for i = 0 to n-1 
    D[A[i]-l] = D[A[i]-l]+1 
for j=1 to u-l D[j] = D[j-1]+D[j] 

for i=n-1 to 0 
    j = A[i]-l 
    S[D[j]-1] = A[i] 
    D[j] = D[j]-1 
return S 

效率萊維丁 - >西塔（N），Johnsonbaugh - > Theta（n + m）m：數組中可清除的整數

所以我的理解是，我選擇的操作最多的是基本操作，我不明白爲什麼當我爲每種算法選擇不同的基本操作時有什麼不同。最終它並不重要，因爲它會導致相同的效率等級，但也許它對於實證分析很重要（比較不同輸入大小所需的基本操作數量）？

我現在要做的是選擇作爲基本操作，它在Algo1中執行5次，在Algo2中執行6次（依賴於循環當然）。這種方法有缺點嗎？

Answer 1

「基本操作」的典型選擇是查看比較次數或交換次數。

考慮一個具有內存層次結構的系統，其中「熱」項目在緩存中，而「冷」項目導致L2未命中，隨後是RAM引用或導致磁盤I/O。然後，高速緩存命中成本可能基本上爲零，基本操作歸結爲高速緩存未命中的成本，導致時間複雜度的新表達式。

大多數排序的列表得到排序more often than you might think。穩定的排序可能比不穩定的排序更容易緩存。如果很容易推斷排序的比較順序如何與高速緩存逐出進行交互，那麼可能會導致對其預期運行時間的很好的大O描述。

編輯：「閱讀A []的元素」似乎是一個公平的操作來談論。 Fancier分析將會看到有多少「A []」操作發生「緩存未命中」。