algorithm - 比较两种算法的复杂度 : Identify Basic Operation applicable for both algorithms?

Question

对于一项作业，我必须从理论上分析两种算法(排序)的复杂性以比较它们。然后我将实现它们并尝试根据经验确认效率。

鉴于此，我分析了这两种算法并且我知道效率等级，但我在识别基本操作时遇到了问题。提示我们在选择基本操作时应该小心，因为它应该适用于两种算法。我的问题是我真的不知道为什么我应该对两种算法采用相同的基本操作。

伪代码

算法 1:

//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]

效率:Theta(n^2)

算法2:

//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

效率 Levitin -> Theta(n), Johnsonbaugh -> Theta(n+m) m:数组中的可区分整数

所以我的理解是，我选择了最常出现的操作作为基本操作，我不明白为什么当我为每个算法选择不同的基本操作时会有差异。最后这无关紧要，因为它无论如何都会导致相同的效率等级，但它可能对实证分析很重要(比较不同输入大小所需的基本操作的数量)？

我现在打算做的是选择赋值作为基本操作，在 Algo1 中执行 5 次，在 Algo 2 中执行 6 次(当然取决于循环)。这种方法有缺点吗？

Answer 1

“基本操作”的典型选择是查看比较次数或交换次数。

考虑一个具有内存层次结构的系统，其中“热”项在缓存中，“冷”项导致 L2 未命中，然后是 RAM 引用，或者导致磁盘 I/O。那么缓存命中成本可能基本上为零，基本操作归结为缓存未命中成本，导致时间复杂度的新表达式。

最有序的列表得到排序 more often than you might think .稳定排序可能比不稳定排序对缓存更友好。如果很容易推断出排序的比较顺序如何与缓存逐出交互，那么就可以很好地对其预期运行时间进行大 O 描述。

编辑:“读取 A[] 的一个元素”似乎是一个值得谈论的公平操作。更高级的分析会查看发生了多少次“A[] 上的缓存未命中”操作。