Как определить трудоемкость составленного алгоритма?

[AlexDem]

незваный гость писал(а):

AlexDem писал(а):

Просто любой дополнительный цикл сложности не выше $O(n)$ увеличит время раза в два (мой - поболе),…

Увеличение в ограниченное число раз (${\rm O}(1)$) нас не волнует — мы говорим об ${\rm O}$.

Тогда нормально, если идея сработает - там всего один проход по array, а count - фиксированной длины. Время увеличится в $O(len) = O(1)$ раз.

[незваный гость]

ок. Дошли руки до кода.

1) Алгорифмом funQSort() пользоваться не рекомендую. Настойчиво не рекомендую. Он может зациклиться при появлении равных элементов в массиве. Правильный алгорифм приведен, например, у Гриса (Наука программирования) и (по-моему, хотя не уверен) у Вирта (Алгоритмы + структуры данных = программы).

Ядро правильного алгорифма — «задача о голландском флаге» — за один проход массива разделить на три зоны: меньше $k$, равно $k$, и больше $k$. После чего сортировать только начало и конец.

2) правильно ли я понимаю, что ‹array› — это сортируемый сегмент ‹base›, а ‹middlle› — ‹midd›? Правильно ли я понимаю, что ‹len› — это длина сортируемого сегмента, а не константа? Правильно ли я понимаю, что Вы используете дополнительную память, пропорциональную длине сортируемого массива? Если последнее верно, то смысл быстрой сортировки теряется: сортировка слиянием дает результат за гарантированное время.

3) Попробуйте покатать свой алгорифм, например, при array[a] = 100 + a. (или -100 + a). Вас ждут сюрпризы.

[AlexDem]

незваный гость писал(а):

1) Алгорифмом funQSort() пользоваться не рекомендую. Настойчиво не рекомендую. Он может зациклиться при появлении равных элементов в массиве.

Можно узнать, в какой именно строке он зацикливается?

незваный гость писал(а):

правильно ли я понимаю, что ‹array› — это сортируемый сегмент ‹base›, а ‹middlle› — ‹midd›? Правильно ли я понимаю, что ‹len› — это длина сортируемого сегмента, а не константа?

"array" соответствует "base", "middle" это "midd". Но "len" это именно константа - длина внутренних массивов "count" и "value", "lenF" в алгоритме сортировки - это другая переменная.

Да, смысл теряется, да, есть сортировка слиянием, но ведь вопрос был не в этом, а можно ли избежать появления $O(n^2)$ при сохранении средней сложности $O(n \log n)$.

незваный гость писал(а):

Попробуйте покатать свой алгорифм, например, при array[a] = 100 + a. (или -100 + a). Вас ждут сюрпризы.

Ага, ждут. Там ещё и "value" надо нулями инициализировать. Но с другой стороны, такой монотонный рост или убывание несложно и отсечь. Или придумать другой вариант - возможно, с несколькими (фиксированным количеством) проходами по массиву.

Добавлено спустя 42 минуты 6 секунд:

незваный гость писал(а):

Правильно ли я понимаю, что Вы используете дополнительную память, пропорциональную длине сортируемого массива?

Нет, это - неверно, там фиксированные массивы. Если бы это было не так, сложность этого добавочного алгоритма уже не была бы $O(n)$.

Добавлено спустя 21 минуту 37 секунд:

Общая идея такова - любой алгоритм, который за фиксированное чило проходов (или итераций вложенного цикла) сможет найти значение вне "плохого" интервала $\delta n$, зависящего от $n$, - подойдёт. Его сложность $O(an)$ сложится с оценкой основного цикла $O(bn)$ и получим: $O(a n) + O(b n) = O((a + b) n) = O(n)$, что с учётом рекурсии даст $O(n \log n)$.

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

[photon]

Возможно здесь найдете что-то: я в этом не спец, но пока искал для себя информацию, случайно наткнулся на эту книгу
http://www.bhargav.com/books/Math/Algorithms_and_Complexity/

[незваный гость]

1) С алгорифмом быстрой сортировки: посмотрите, как он будет себя вести на массиве из 0.

2) К выбору среднего элемента. Я был неправ, в том смысле, что существуют алгорифмы оптимального и квазиоптимального выбора среднего. Например, мы можем отсортировать сегмент, и выбрать середину в качестве среднего элемента, что приведет к общей оценке в худшем случае ${\rm O}(n (\log n)^2)$. Другой вопрос, насколько практичны такие алгорифмы? Если нам нужно гарантированное время, проще использовать пирамидальную сортировку, а если неважно — быстрая сортировка (с минимальными ухищрениями) быстрее. Я, впрочем, сомневаюсь, что можно за линейное время гарантированно найти более чем конечный элемент (но и тут могу быть не прав).

[AlexDem]

незваный гость писал(а):

С алгорифмом быстрой сортировки: посмотрите, как он будет себя вести на массиве из 0.

На массиве из всех одинаковых элементов я уже прогнал на всякий случай (из нулей у меня без переделки затруднительно) - всё нормально. Там играет то, что при сравнении элементов стоит строго больше и строго меньше, и ниже, где "/* Swap improper elements */", есть проверка "if (eleL <= eleH) {". Это переделка довольно обкатанного алгоритма, не думаю, что он сбойный. Но как-нибудь попробую.

незваный гость писал(а):

Я, впрочем, сомневаюсь, что можно за линейное время гарантированно найти более чем конечный элемент (но и тут могу быть не прав).

Ну, у меня тоже есть сомнения, но я не знаю ни как их доказать, ни как опровергнуть . Похоже, нарыли интересную тему. Насчёт практического использования - не знаю, если бы было очень нужно, то была бы какая-нибудь информация...

[незваный гость]

Я испытываю некоторые проблемы с пониманием приведенного ВАми алгорифма.

После перевода на Python и добавления тестирующего кода, текст выглядит так:

compares = 0
swaps = 0

def funQSort(base, limL, limH):
  global compares, swaps

  while limL < limH:
    ## Initialize variables
    eleL = limL; eleH = limH
    midd = base[(eleL + eleH) >> 1]

    ## Compare rows
    while eleL < eleH:
      ## Compare elements
      compares += 1
      while base[eleL] < midd:
        eleL += 1
        compares += 1

      compares += 1
      while base[eleH] > midd:
        eleH -= 1
        compares += 1

      if eleL <= eleH:
        base[eleL], base[eleH] = base[eleH], base[eleL]
        eleL += 1
        eleH -= 1
        swaps += 1

      ## Recurrent lower iteration
      if eleH > limL:
        funQSort(base, limL, eleH);

      ## Next higher iteration
      limL = eleL;

def test():
  global compares, swaps

  for n in range(1, 30+1):
    compares = 0; swaps = 0
    funQSort([0] * n, 0, n-1)
    print n, compares, swaps

test()

Результат впечатляет: сложность [strike]скорость[/strike] сортировки растет примерно как число Фибоначи (и число сравнений, и число перестановок)! То есть, экспоненциально! Я полагаю, дело в организации рекурсии.

n       compare    swap
1          0         0
2          2         1
3          6         3
4         12         6
5         24        12
6         42        21
7         74        37
8        124        62
9        212       106
10       350       175
11       582       291
12       952       476
13      1568       784
14      2554      1277
15      4174      2087
16      6780      3390
17     11044      5522
18     17914      8957
19     29098     14549
20     47152     23576
21     76484     38242
22    123870     61935
23    200726    100363
24    324968    162484
25    526312    263156
26    851898    425949
27   1379198    689599
28   2232084   1116042
29   3612904   1806452
30   5846610   2923305

[PAV]

незваный гость писал(а):

скорость сортировки растет

Не понял - скорость растет или время?

[незваный гость]

сложность. Виноват-с. Поправлю-с.

[AlexDem]

А как в Python закрываются циклы?
С рекурсией проблем быть не должно, там одна ветка заменена итерацией. Но я не пойму, как определяется конец циклов в Вашем примере.

[незваный гость]

отступом. В Python отступ определяет структуру программы.

В этом и была моя ошибка при переводе: рекурсия оказалась во внутреннем цикле. Пойду думать дальше.

Добавлено спустя 33 минуты 42 секунды:

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

[AlexDem]

Не знаю, сумел ли объяснить - привожу текст с комментариями. Перевёл на сравнение целых и вернул вторую ветку рекурсии на своё место, убрав охватывающий цикл.

void funQSort(
    int            base[],
    const int      limL,
    const int      limH)
{
    int            eleL, eleH;
    int            midd, swap;

    /* Initialize variables */
    eleL = limL;
    eleH = limH;
    midd = base[(eleL + eleH) >> 1];

    /* Начинаем сравнение с концов интервала до тех пор, пока указатели
        не сойдутся (или даже не перехлестнутся) */
    while (eleL < eleH) {
        /* Сравниваем элементы слева, пока они меньше midd. На каком-то
            элементе гарантировано остановимся, т.к. по крайней мере сам
            midd в массиве точно есть */
        while (base[eleL] < midd) {
            eleL++;
        }

        /* Сравниваем элементы справа, пока они больше midd. На каком-то
            элементе гарантировано остановимся по той же причине */
        while (base[eleH] > midd) {
            eleH--;
        }

        /* Когда мы оказались здесь, eleL указывает на элемент больший или
            равный midd, а eleH - на меньший или равный midd. Но возможна
            ситуация, когда указатели перехлестнутся. Например, если midd = 10,
            а между указателями оказались необработанными значения в
            квадратных скобках: 1 [7 6 5] 11 (причём eleL в начале итерации
            смотрел на 7, а eleH - на 5; 1 и 11 - края уже обработанных
            интервалов). Тогда первый цикл установит eleL на 11, а второй -
            оставит eleH на 5, то есть eleL залезет в уже обработанный интервал.
            Если следующую проверку не сделать, получим: (... 1 7 6 11)(5 ...),
            вместо нужного (... 1 7 6 5)(11 ...) */

        /* Эта проверка нужна на случай перехлёста указателей. Здесь есть
            некоторый минус - элементы будут переставляться, даже если
            base[eleL] == base[eleH] == midd. Но лишние условия снижают
            производительность, и даже это условие можно бы переместить и
            поставить после цикла - просто в случае перехлёста переставить
            элементы и указатели обратно. */
        if (eleL <= eleH) {
            swap = base[eleL];
            base[eleL] = base[eleH];
            base[eleH] = swap;
            eleL++;
            eleH--;
        }
    }

    /* Здесь eleL всегда больше или равен eleH (то есть левый указатель стоит
        правее или на правом) - см. условие главного цикла сравнений. Поэтому
        перекрытия интервалов быть не может (только если на один элемент). */

    /* Сортируем левую половину */
    if (eleH > limL) {
        funQSort(base, limL, eleH);
    }

    /* Сортируем правую половину */
    if (eleL < limH) {
        funQSort(base, eleL, limH);
    }
}

[незваный гость]

Спасибо за комментарии.

Добавлено спустя 36 минут 57 секунд:

Года полтора назад мне показали следующий алгоритм на Жабе:

     private static <T> void quickSortHelper(T[] array, int start, int end){
        if (start >= end) {
            return;
        }

        int pivot = selectPivot(array, start, end);

        int left = start;
        int right = end - 1;

        while (left <= right) {
            if(comp.compare(array[left], array[pivot]) <= 0) {
                left++;}
            if(comp.compare(array[right], array[pivot]) >= 0) {
                right--;
            } else {
                swap(array, left, right);
                left++;
                right--;
            }
        }

        if (pivot < right) {
            swap(array, right, pivot);
            pivot = right;
        } else if(pivot > left) {
            swap(array, left, pivot);
            pivot = left;
        }

        quickSortHelper(array, start, pivot);
        quickSortHelper(array, pivot + 1, end);
    }

Как видите, он совсем мало отличается от того, что у Вас. За одним важным исключением: он не работает. Я запомнил, что с алгоритмом есть проблемы, и увидев Ваш код (который очень похож структурно), скоропалительно высказался. О чем сожалею.

[AlexDem]

Не берите в голову .

Если не ошибаюсь, то с тем алгоритмом проблема в том (возможно - и не одна), что он не переставляет элемент, равный "array[pivot]" с меньшим (или большим), когда такая перестановка нужна. Например, имеем массив:
12 10 10

Средним элементом он выберет 10 (индекс = 2). Потом переставит 12 с 12-ю же. После чего индекс "left" будет равен 2, а индекс "right" равен 0. (Здесь и далее - индекс первого элемента = 1, а 0 - уже выход за границы).

Условия после цикла ничего не изменят - они не выполняются. Потом пойдём сортировать половинки: (12 10) и (10). Рассмотрим первую. Там ещё при инициализации странно выглядит "right = end - 1" - непонятно, зачем это. Если с этим вычитанием - то ясно, что ничего не отсортируем.

Если без него - индекс "pivot" = 1, переставим 10 с 10-ю же, после цикла индексы "left" = 3, "right" = 1. Последующие условия не выполняются, и уже больше ничего не сортируется.

В результате получим тот же массив: 12 10 10. Может, там ещё какие сложности есть - не разобрался с этими условиями после цикла, возможно, там знаки ">" и "<" перепутаны. Вообще, похоже, автор ожидал, что средний по счёту элемент будет и средним по значению - там половинки берутся по индексу "pivot".
Есть такой анекдот:

Цитата:

Сидит программист глубоко в отладке. Третий день сидит. Ничего не получается. Подходит к нему сынишка, и говорит:
- Папа, а почему солнце встает на востоке?
- Ты это проверял?
- Да.
- Работает?
- Да.
- Каждый день работает?
- Да.
- Тогда сынок, ради бога, ничего не трогай, ничего не меняй!