Большой тэта нотации и сортировки выбора

Question

Какова будет сложность для наилучшего и наихудшего случаев в Big-Theta (T) нотации алгоритма сортировки выбора, когда массив увеличивается путем многократного добавления 19?

Например:

[ 19, 13, 7, 19, 12, 16, 19 ],
[ 19, 13, 7, 19, 12, 16, 19, 19 ],
[ 19, 13, 7, 19, 12, 16, 19, 19, 19 ]

и так далее.n используется для представления длины массива.

Таким образом, мы добавляем одно и то же число в конец массива, но это число также оказывается наибольшим, поэтому оно останется вконец массива.Означает ли это, что это не влияет на эффективность?Я очень смущен.

Answer 1

по возрастанию,

1. Найти минимальное значение в списке
2. Поменяйте местами со значением в первой позиции
3. Повторите шаги выше для оставшейся части списка (начиная с вторая позиция и продвижение каждый раз)

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

A - an array containing the list of numbers
numItems - the number of numbers in the list

for i = 0 to numItems - 1
    for  j = i+1 to numItems               
        if A[i] > A[j]
            // Swap the entries
            Temp = A[i]
            A[i] = A[j]
            A[j] = Temp          
        End If    
    Next j
Next i

Как вы можете видеть вышеупомянутый псевдокод, оба цикла итерируют до конца своих ограничений без каких-либо условий. Так что это дает θ(n²). Тем не менее, O(n) в среднем, θ(n) наихудших и θ(1) лучших случаев для обстоятельств свопинга.

Answer 2

Нет, это не влияет на эффективность.

При сортировке выбора производительность равна N ^ 2 из-за вложенных циклов. Даже если элементы в конце не нужно менять местами, циклы все равно будут сравнивать их.

Итак, чтобы ответить на ваш точный вопрос: поскольку наилучший случай, наихудший случай и средняя производительность - это все N ^ 2, и это не влияет на эффективность, никаких изменений в производительности нет.