算法分析中什么算作比较？

Question

主要问题：在跟踪比较时，什么才是真正的比较？我应该只计算数组项之间的比较，因为这是算法的目的，还是更广泛地接受计算每一个比较？

目前，我正在努力解决一个事实，即有人告诉我 最坏情况 冒泡排序算法的理论比较次数如下：

Amount of comparisons:

(N-1) + (N-2) + (N-3) + ... + 2 + 1 = (N*(N-1))/2 = (N^2-N)/2 < N^2

所以根据公式 (N^2-N)/2，输入大小 (N) 为 10，我将得到总共 45 次比较。但是提到这个计算只适用于这段伪代码内循环的比较操作：

for i:=1 to N-1 do 
{
    for j:=0 to N-i do
    {
        if A[j] > A[j+1] // This is the comparison that's counted.
        {
            temp := A[j]
            A[j] := A[j+1]
            A[j+1] := temp
        }
    }
}

现在 Java，我的代码如下所示：

public int[] bubble(int[] array) 
    {
        int comparisons = 0;
        int exchanges = 0;
        int temp;
        int numberOfItems = array.length;
        boolean cont = true;  
        
        comparisons++; // When pass == numberOfItems, a comparison will be made by the for loop that wouldn't otherwise be counted.
        for (int pass=1; pass != numberOfItems; pass++) 
        { 
            comparisons = comparisons + 2; // Counts both the outer for loop comparison and the if statement comparison.

            if (cont) // If any exchanges have taken place, cont will be true.
            {    
                cont = false;  
                comparisons++; // Counts the inner for loop comparison

                for (int index = 0; index != (numberOfItems - pass); index++) 
                {
                    comparisons++; // Counts the if statement comparison.

                    if (array[index] > array[index+1]) 
                    {
                        temp = array[index];
                        array[index] = array[index+1];
                        array[index+1] = temp;
                        cont = true;
                        exchanges++;
                    }  // end inner if              
                }  // end inner for            
            }
            else
            {
                break;  // end outer if
            }
        }      
        
        System.out.println("Comparisons = " + comparisons + "\tExchanges = " + exchanges);
        return array;
    }

在对我的代码执行最坏情况后（使用一个包含 10 个元素的数组，顺序相反），我总共进行了 73 次比较。这似乎是对 45 次比较的理论结果的疯狂高超调。这对我来说是正确的，因为我已经考虑了所有 for 循环和 if 语句。

非常感谢任何帮助！

编辑： 我注意到我的内部循环的总比较计数有误。我之前两次计算内部循环，但现在它是固定的。而不是得到118个比较，我现在得到73个。但是，问题仍然存在。

Answer 1

比较变量只应在代码执行到 if 语句后递增。仅当满足外部和内部 for 循环中规定的条件时才会达到 if 语句，因此代码应该是这样的。也不要忘记将 for 循环中的条件从使用 != 更改为 <= 新的 java 代码：

public int[] bubble(int[] array) 
   {
        int comparisons = 0;
        int exchanges = 0;
        int temp;
        int numberOfItems = array.length;
        boolean cont = true;  


        for (int pass=1; pass <= numberOfItems; pass++) 
        { 


            if (cont) // If any exchanges have taken place, cont will be true.
            {    
                cont = false;  

                for (int index = 0; index <= (numberOfItems - pass); index++) 
                {

                    if (array[index] > array[index+1]) 
                    { comparison++;
                        temp = array[index];
                        array[index] = array[index+1];
                        array[index+1] = temp;
                        cont = true;
                        exchanges++;
                    }  // end inner if              
                }  // end inner for            
           }

        }     
         comparison++; // here you increment by one because you must also count the comparison that failed

        System.out.println("Comparisons = " + comparisons + "\tExchanges = " + exchanges);
        return array;
    }

Answer 2

在评估排序算法时，通常将数组元素之间的所有比较都算作具有等效成本，而忽略数组索引等事物之间的比较。基本概念是，为了使排序操作与基数分区保持明显不同，被排序项目的大小需要随着项目数量的增加而增加。例如，假设有一个包含 1,000,000,000 char 个值的数组，并且想要对它们进行排序。虽然可以使用快速排序、冒泡排序或其他方法，但更快的方法是使用 int[65536] 并计算每个值的数量。即使需要对具有 char 键的项目进行排序，最好的方法是确定将最后一个键为 0 的项目放在哪里（键为零的项目数减一)，将最后一个键为 1 的项目放在哪里（键为 0 或 1 的项目数减一），等等。所有这些操作所花费的时间与项目数加上可能键值的数量成正比，没有任何 lg(N) 因素。

请注意，如果忽略 "bookkeeping" 成本，像 Quicksort 这样的算法并不是最优的。旨在最大化从每次比较中获得的信息量的排序算法可能会进行较少的比较。然而，除非比较非常昂贵，否则这种排序算法在 "smart" 上浪费的时间可能比在 "stupid".

上浪费的时间更多

有一个问题我没有看到太多讨论，但我认为它可以在许多现实世界的案例中提供显着的好处，那就是优化已知在一个狭窄范围内的项目之间的比较序列。如果在对一系列包含千个字符的路径名称执行快速排序时，正在处理一个分区，其条目在共享前 950 个字符的两个名称之间都是已知的，则无需检查任何名称的前 950 个字符在那个分区。除非密钥长度是一个参数，否则此类优化在大 O 术语中不太可能有意义，但在现实世界中，我希望它有时会产生数量级的影响。

Answer 3

测量排序中的比较次数时，您只计算数组项之间的比较次数。当你比较它们时，不管它们是否真的在数组中，你都会计算它们。

想法是，数组可能包含需要很长时间才能比较的内容，而不是简单的整数。例如，可以使用 N(N-1)/2 string 比较对字符串数组进行冒泡排序，即使单个字符串比较可能需要许多其他操作，包括许多个字符的比较。

根据比较次数来衡量排序算法的性能，使衡量结果与被排序事物的类型无关。

算法分析中什么算作比较？

What counts as a comparison in algorithm analysis?

java

algorithm

analysis