performance - 为什么在评估算法效率时通常将比较作为基本操作？

Question

我目前正在了解各种基本算法(排序、搜索等)，我发现大多数书籍都在谈论计算所述算法的效率(O(n logn) 等)。

有些作者在计算这些的时候，通常把比较称为Basic Operation(最昂贵)，然后计算整个算法出现了多少个，最后给它一个渐近符号。

例如，对于暴力选择排序，这是我在 Wikipedia 上看到的算法:

int i,j;
int iMin;

for (j = 0; j < n-1; j++) {
    iMin = j;
    for ( i = j+1; i < n; i++) {
        if (a[i] < a[iMin])
            iMin = i;
    }

    if(iMin != j)
        swap(a[j], a[iMin]);
}

对其效率的分析是这样说的:

Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and so on, for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n^2) comparisons (see arithmetic progression). Each of these scans requires one swap for n − 1 elements (the final element is already in place).

如果我错了请纠正我，但在我看来比较 a[i] < a[iMin]被认为是这里最昂贵的操作。

为什么不是 for 循环头中的比较和递增，以及交换操作？

附注:我知道这个网站上有数百个关于每个渐近符号的含义/代表的问题，但这不是我要问的。我也知道有更有效的排序算法，但这也不是我要问的。

Answer 1

实现算法的循环和其他代码基础结构与比较次数成正比。粗略地说，对于循环的每次迭代，都会进行比较。交换操作将以与比较不同的比例发生，并且每个项目需要一些其他数量的工作。实际上，这意味着每次比较的实际机器指令数大于比较本身的工作量。然而，这不是大 O 表示法的重要部分。

整个目的是描述两种不同输入大小之间的增长率。每个项目的工作是每次比较两条指令还是四条指令并不重要。如果算法为 O(n^2) 并且您的输入 n 为 100，则差值为 20000 至 40000。如果输入为 1000，则为 2000000 至 4000000。将其与 O(n*Log(n)) 进行比较是 (2 * 3 * 1000) 与 (4 * 3 * 1000)。显然，重要的部分是零的个数，而不是前导数字。

换句话说，您可以通过购买速度提高一倍的计算机来解决 2 比 4 的问题。您无法通过这种方式解决算法之间的差异。实现算法总是需要一些计算工作系数。别担心；担心必须多久执行一次该工作。