На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Быстрая сортировка , Поиск "плохого" теста
    Известно, что у "быстрой" сортировки (QuickSort) среднее число сравнений пропорционально O(N*logN). Хотя с дополнением, что для некоторых случаев оно стремится к O(N^2). Но нигде не сказано, как получить такой пример! mad.gif
    Мой вопрос сводится к тому, как работают генераторы "плохих" тестов для сортировок. Можно ли написать программу, которая для некоторго метода сортировки с сложностью O(N*logN) выдает пример входных данных, при которых сложность становится O(N^2)?
      помоему ето ересь!! у быстрой сортировки не может быть больше чем O(N*logN)! наверное ето ещё у какоголибо метода
        2 wormball
        В быстрой сортировке массив разделяется на 2 части: элементы, меньшие заданного ключа - в одну, а большие - в другую. Потом эти части сортируются отдельно и склеиваются вместе. Фишка в том, что может получиться так, что на каждом шаге массив из N элементов будет делиться на 2 подмассива: из 1 элемента и из (N - 1) элемента. Так понадобится O(N) сортировок, что дает суммарное время O(N^2).
        O(N*logN) - это когда массив всегда делится на 2 примерно равные по размеру части.

        2 Lucifer:
        Это серьезно, или тонкий юмор?!

        Вот, например, какой самый "плохой" тест для quicksort-а из Паскаля?

        procedure quicksort(var a: list; Lo,Hi: integer);

        procedure sort(l,r: integer);
        var
         i,j,x,y: integer;
        begin
         i:=l; j:=r; x:=a[(l+r) DIV 2];
         repeat
           while a[i]<x do i:=i+1;
           while x<a[j] do j:=j-1;
           if i<=j then
           begin
             y:=a[i]; a[i]:=a[j]; a[j]:=y;
             i:=i+1; j:=j-1;
           end;
         until i>j;
         if l<j then sort(l,j);
         if i<r then sort(i,r);
        end;
          А причем здесь мама и папа?

          PS: тема уходит в offtopic...
            ну тогда я думаю ето просто числа, расположенные в обратном порядке.
              Тогда quicksort из раскидает за один проход! biggrin.gif biggrin.gif biggrin.gif
              Т.е. более N сравнений, IMHO, не будет.
                Да не обязательно в обратном... Просто в некоторых реализациях быстрой сортировки медиана (тот елемент, справа от которого и слева от которого...) выбирается случайным образом. Поетому генератором "плохих" входных последовательностей, на самом деле является математический объект, который фсе привыкли называть "демон". Ен точно знает, какая последовательность будет самой плохой. И неважно откуда, лишь бы выполнялось условие существования етой самой плохой последовательности. smile.gif

                Если медиана выбирается каким-то определенным образом, надо разместить елементы массива так, чтобы ета самая медиана не делила массив на части. (т.е., всегда оказывалась минимальным или максимальным елементом сортируемой подпоследовательности).
                Сообщение отредактировано: Visitor -
                  Цитата
                  Visitor, 11.12.03, 15:22
                  математический объект, который фсе привыкли называть "демон"

                  ты ещё скажи шайтан smile.gif
                  тогда наоборот: чтобы они уже были в правильном порядке рассортированы. тоесь она поймёт, что все последующие числа больше первого, и честно вызовет саму себя с массивом, меньшим на один элемент. кстати если они в обратном порядке, так тоже произойдёт. smile.gif
                    Не, тогда сложность логарифмической останется....
                      Ура! Нашел генерилку! Кому интересно, сюда!
                        Цитата
                        Visitor, 11.12.03, 16:07
                        Не, тогда сложность логарифмической останется....

                        почему??
                          Дык массив так и будет делиться пополам на каждой итерации...
                            в томто и дело, что так он будет делиться не пополам, а будет делиться на часть нулевого размера и часть, где будет почти весь массив. а потому она претерпит n самовызовов, и сложность будет n^2. cool.gif
                              Да, можно в процедуру сортировки вставлять проверку "а не отсортирован ли уже массив?", и тогда некоторые часные случаи будут обрабатываться сами собой. Обычно для алгоритмов сортировки условие конца работы несколько проще.
                                ну ето будет имхо глупость, так ещё более замедлится. можно делить не первым, а средним элементом. а есь ещё помнится двухсторонняя быстрая сортировка.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0350 ]   [ 16 queries used ]   [ Generated: 19.03.24, 10:04 GMT ]