比较两种算法的复杂度:识别适用于两种算法的基本操作？

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]

效率: Theta(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

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

因此，我的理解是，我选择最基本的运算作为基本运算，我不明白为什么当我为每种算法选择不同的基本运算时，会有什么不同。最后，它并不重要，因为它将导致相同的效率类，但也许它对实证分析(比较不同输入大小所需的基本操作数)很重要？

我现在计划做的是选择赋值作为基本操作，在Algo1中执行5次，在Algo 2中执行6次(当然依赖于循环)。这种方法有什么坏处吗？

Answer 1

“基本操作”的典型选择是查看比较或掉期的数量。

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

主要是排序列表得到排序，比你想象的还要频繁。稳定的排序可能比不稳定的排序更有利于缓存。如果很容易解释一个排序的比较顺序如何与缓存驱逐交互，那么这可能会导致对其预期运行时间的很好的大O描述。

编辑：“阅读A[]的一个元素”似乎是一个公平的操作。更有价值的分析将看到有多少“缓存丢失在A[]上”操作发生。