比较两种算法的复杂性：确定适用于两种算法的基本操作？

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 []”操作发生“缓存未命中”。