Что считается сравнением в алгоритме анализа?

Question

ОСНОВНОЙ ВОПРОС: При отслеживании сравнений что фактически считается сравнением? Должен ли я считать только сравнения между элементами массива, поскольку именно для этого и предназначен алгоритм, или более широко принято считать каждое отдельное сравнение?

В настоящее время я пытаюсь осознать тот факт, что я сказал, что теоретическое число сравнений для алгоритма пузырьковой сортировки наихудший случай выглядит следующим образом:

Количество сравнений:

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

Таким образом, согласно формуле (N ^ 2-N) / 2, с размером ввода (N), равным 10 , я получил бы в общей сложности 45 сравнений. Однако упоминается, что этот расчет применяется только к операции сравнения во внутреннем l oop этого псевдокода:

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 сравнений. Это мне кажется правильным, поскольку я учел все циклы и операторы if.

Любая помощь очень ценится!

РЕДАКТИРОВАТЬ: Я заметил ошибку в моем общем счете сравнения для моего внутреннего l oop. Раньше я дважды считал внутренний l oop, но теперь он исправлен. Вместо 118 сравнений я получаю 73. Однако вопрос все еще стоит.

Answer 1

При оценке алгоритмов сортировки принято считать все сравнения между элементами массива как имеющие эквивалентную стоимость, игнорируя при этом сравнения между такими вещами, как индексы массива. Основная концепция c заключается в том, что для того, чтобы операции сортировки оставались отчетливо отличающимися от радикального разделения, размер сортируемых элементов должен был бы увеличиваться с увеличением их количества. Предположим, например, что у одного есть массив значений 1,000,000,000 char, и он хочет отсортировать их. В то время как можно использовать быструю сортировку, пузырьковую сортировку или что-то еще, более быстрый подход будет состоять в том, чтобы просто использовать int[65536] и подсчитать, сколько существует каждого значения. Даже если нужно отсортировать элементы с ключами char, лучший способ сделать это - определить, куда поместить последний элемент с ключом 0 (количество элементов с ключом ноль, минус один), где разместить последний элемент с ключом 1 (количество элементов с ключами 0 или 1, минус один), et c. Все такие операции будут занимать время, пропорциональное количеству элементов плюс количество возможных значений ключа, без какого-либо фактора lg (N).

Обратите внимание, что если игнорировать затраты на «бухгалтерию», такие алгоритмы, как Quicksort, не являются вполне оптимально. Алгоритм сортировки, предназначенный для максимизации объема информации, получаемой при каждом сравнении, может выполнять несколько меньших сравнений. Однако, если сравнение не очень дорогое, такой алгоритм сортировки, скорее всего, будет тратить больше времени на то, чтобы быть «умным», чем на «глупость».

Одна проблема, которую я не видел, обсуждалась много, хотя я бы Я думаю, что это может принести значительную пользу во многих реальных случаях, будет оптимизировать последовательности сравнений между предметами, которые, как известно, находятся в узком диапазоне. Если при выполнении быстрой сортировки для серии имен путей из тысячи символов обрабатывается раздел, все записи которого известны между двумя именами, которые разделяют первые 950 символов, нет необходимости проверять первые 950 символов любых имен в этом разделе. Такая оптимизация вряд ли будет иметь смысл в терминах big-O, если только длина ключа не является параметром, но в реальном мире я ожидаю, что она иногда может оказывать влияние на порядок.

Answer 2

При измерении количества сравнений в сортировке вы учитываете только сравнения между элементами массива. Вы подсчитываете их, действительно ли они находятся в массиве, когда сравниваете их.

Идея состоит в том, что вместо простых целых чисел массив может содержать вещи, для сравнения которых требуется много времени. Например, массив строк может быть отсортирован по пузырьку, используя сравнения N (N-1) / 2 строка , даже если для сравнения одной строки может потребоваться множество других операций, включая many сравнения отдельных символов.

Измерение производительности алгоритма сортировки по количеству сравнений делает измерение независимым от типа сортируемых вещей.

Answer 3

переменная сравнения должна увеличиваться только после достижения оператора if при выполнении кода. Оператор if достигается только в том случае, если выполнены условия, указанные во внешнем и внутреннем для l oop, поэтому код должен быть таким. Также не забудьте изменить условие в циклах for, используя! = To <= Новый java код: </p>

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;
    }