Какова средняя большая сложность рода Gnome?

Question

В википедии об этом ничего нет.
Кто-нибудь знает это?

Я хочу знать только среднюю сложность Big-O этого алгоритма.

Answer 1

Производительность алгоритма сортировки гномов не менее O(f(n)), где f(n) - сумма для каждого элемента во входном списке расстояния до места, где этот элемент должен оказаться. Для «случайного» списка длиной L ожидается, что элемент в начале списка будет в среднем на расстоянии L / 2 от своего отсортированного местоположения. Ожидается, что элемент в середине списка будет в среднем на расстоянии L / 4 от своего отсортированного местоположения. Так как всего L элементов, f(n) составляет не менее L * L / 4. Поэтому в среднем сортировка гномов составляет O(n * n).

Извините, если за этим трудно следовать.

Answer 2

Вот простое сравнение массива случайных значений в виде пузырьков и гномов, значений в обратном порядке, 3 объединенных массивов упорядоченных значений и упорядоченных значений.Сортировка гномов в среднем кажется немного дешевле с точки зрения сравнения.

Обратите внимание, что сравнения / свопы при сортировке случайных значений всегда немного отличаются, но близки к этим результатам.

N = 100, попыток = 1000

в случайном порядке:

пузырьковая сортировка: сравнения = 8791794, обмены = 2474088

сортировка гномов: сравнения = 5042930, обмены = 2474088

в обратном порядке:

пузырьковая сортировка: сравнения = 9900000, обмены = 4950000

сортировка гномов: сравнения = 9900000, обмены = 4950000

3 упорядоченных набора:

пузырьковая сортировка: сравнения = 6435000, свопы = 1584000

сортировка гномов: сравнения = 3267000, обмены = 1584000

упорядочено:

пузырьковая сортировка: сравнения = 99000, swaps = 0

сортировка гномов: сравнение = 99000, swaps = 0

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

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int N = 100;
int x[N];

int main()
{
    srand((unsigned int)time(0));

    int comparisons = 0;
    int swaps = 0;

    int attempts = 1000;
    while (--attempts >= 0)
    {
        // random:
        for (int i = 0; i < N; ++i)
            x[i] = rand();

        // reversed:
        /*for (int i = 0; i < N; ++i)
            x[i] = N - 1 - i;*/

        // 3 ordered sets:
        /*for (int i = 0; i < N/3; ++i)
            x[i] = i;
        for (int i = N/3, j = 0; i < 2*N/3; ++i, ++j)
            x[i] = j;
        for (int i = 2*N/3, j = 0; i < N; ++i, ++j)
            x[i] = j;*/

        // ordered:
        /*for (int i = 0; i < N; ++i)
            x[i] = i;*/

        // bubble sort:
        /*{
            bool swapped;
            do
            {
                swapped = false;
                for (int i = 0; i < (N - 1); ++i)
                {
                    ++comparisons;

                    if (x[i] > x[i + 1])
                    {
                        ++swaps;

                        int t = x[i];
                        x[i] = x[i + 1];
                        x[i + 1] = t;
                        swapped = true;
                    }
                }
            } while (swapped);
        }*/

        // gnome sort:
        {
            int i = 1;
            while (i < N)
            {
                ++comparisons;

                if (x[i] >= x[i - 1])
                    ++i;
                else
                {
                    ++swaps;

                    int t = x[i];
                    x[i] = x[i - 1];
                    x[i - 1] = t;
                    if (i > 1)
                        --i;
                }
            }
        }
    }

    printf("comparisons = %d\n", comparisons);
    printf("swaps = %d\n", swaps);
}

Очевидноэто далеко не полный тест, но он дает представление.

Answer 3

Мне кажется интуитивно понятным, что если сортировка вставки имеет среднее время выполнения O (n ^ 2), а сортировка gnome является несколько худшей версией сортировки вставки, то среднее время выполнения сортировки gnome также будет равно O (n ^ 2) (ну, Θ (n ^ 2)).

В этом pdf есть что сказать о среднем содержании вставки-сортировки , равном Θ (n ^ 2):

Доказательство этого не тривиально, но это основано на интуитивном факте, что в среднем тест цикла while "list [pos-1]> value" верно для половину времени, так что в среднем количество выполнений цикла while это половина от максимального числа. Поскольку максимальное число составляет n (n-1) / 2, среднее количество казней цикл while равен n (n-1) / 4, что все еще Θ (n ^ 2).

То же самое относится и к сортировке гномов. Вы знаете, сортировка gnome не может быть лучше, потому что "gnome" сначала должен сканировать в обратном направлении (путем замены), чтобы найти, куда идет элемент (эквивалентно сканированию вставки с сортировкой вперед), а затем должен идти вверх по списку, просматривая элементы что это уже отсортировано. Любые различия во времени выполнения между методами сканирования, на мой взгляд, незначительны для предела сложности, но я постараюсь доказать это.

Answer 4

«Среднее» действительно невозможно ответить, не взглянув на входные данные. Если вы знаете, что сортируете, вы могли бы провести некоторый анализ, чтобы лучше понять, как он будет работать в вашем приложении.

Answer 5

http://en.wikipedia.org/wiki/Gnome_sort

Это O(n^2). В худшем случае, каждый раз, когда вы вводите текущую позицию, необходимо поменять ее на предыдущую, из-за чего позиция уменьшается, и вам приходится снова обмениваться. Проверьте сортировку по возрастанию в отсортированном по наследству массиве (т. Е. Чтобы получить [1 2 3 4] из [4 3 2 1], у вас будет наихудший случай).

Answer 6

Скорее наоборот, Википедия говорит, что это O (n ² ), и из описания я не могу понять, как возникли бы реальные сомнения по этому поводу.

Answer 7

Википедия ясно говорит, что у нее наихудшее время выполнения O (n ** 2).