Какова временная сложность следующей функции сортировки? - PullRequest
Новая
       16

Какова временная сложность следующей функции сортировки?

0 голосов
/ 26 декабря 2018

Я написал этот код для пузырьковой сортировки. Может кто-нибудь объяснить мне сложность времени для этого.Это работает как 2 для петель.Но все же хочу подтвердить со временем сложность. 

public int[] sortArray(int[] inpArr)
{
    int i = 0;
    int j = 0;
    while(i != inpArr.length-1 && j != inpArr.length-1)
    {
        if(inpArr[i] > inpArr[i+1])
        {
            int temp = inpArr[i];
            inpArr[i] = inpArr[i+1];
            inpArr[i+1] = temp;
        }
        else
        {
            i++;
        }

        if(i==inpArr.length-1)
        {
            j++;
            i = 0;
        }
    }

    return inpArr;
}

Ответы [ 2 ]

0 голосов
/ 26 декабря 2018

Ваша временная сложность O(n^2) в худшем случае и O(n) в лучшем случае.Ваш средний сценарий все еще выполняет O (n ^ 2) сравнений, но будет иметь меньше свопов, чем O (n ^ 2).Это потому, что вы, по сути, делаете то же самое, что и два for цикла.Если вы заинтересованы в алгоритмической эффективности, я бы порекомендовал проверить уже существующие библиотеки такого рода.Компьютерные ученые, работающие над подобными вещами, действительно интенсивны. Метод Java Arrays.sort() основан на проекте Python под названием timsort , который основан на сортировке слиянием.Недостаток вашего (и каждого) типа Bubble в том, что он действительно неэффективен для больших неупорядоченных массивов.Подробнее здесь .

0 голосов
/ 26 декабря 2018

Это будет иметь O (n ^ 2) временную сложность.На самом деле, это, вероятно, будет и O (n ^ 2), и тета (n ^ 2).

Посмотрите на логику вашего кода.Вы выполняете следующее:

  1. Цикл по массиву ввода
  2. Если текущий элемент больше следующего, переключите два
  3. Если это неВ этом случае увеличьте индекс (и, по сути, проверьте следующий элемент, так что рекурсивно пройдитесь по шагам 1-2)
  4. Как только ваш индекс равен длине 1 входного массива, т.е. он прошел весь массив,ваш индекс сбрасывается (строка i=0), увеличивается j, и процесс перезапускается.

Это, по сути, гарантирует, что данный массив будет циклически повторен дважды, что означает, что у вас будетWORST-CASE (big o или O (x)) временная сложность O (n ^ 2), но, учитывая этот код, ваша СРЕДНЯЯ (тета) временная сложность будет тета (n ^ 2).

Есть НЕКОТОРЫЕ ситуации, когда вы можете иметь ЛУЧШИЙ СЛУЧАЙ (лямбда) n lg (n), что дает лямбда (n lg * (n)) временную сложность, но эта ситуация редка, и ядаже не уверен, что это возможно с помощью этого кода.

...