0
Показать результат работы Shell Sort на входе 9,8,7,6,5,4,3,2,1 с использованием приращений {1,3,7}.Проблема с сортировкой Shell
Я сделал эту часть. результат:
9 8 7 6 5 4 3 2 1 (original)
2 1 7 6 5 4 3 9 8 (7-sort)
2 1 4 3 5 7 6 9 8 (3-sort)
1 2 3 4 5 6 7 8 9 (1-sort)
Тогда вопрос требует от меня, чтобы определить время выполнения сортировки Шелла с помощью приращений Shell по N/2, N/4, ..., 1 для отсортированного ввода.
Я не совсем уверен, как ответить на второй вопрос, поскольку я не понимаю требования этого вопроса. Итак, кто-нибудь даст какие-то намеки, чтобы я мог закончить этот вопрос? Благодарим вас за помощь!
Я вижу вашу точку зрения. Теперь я понимаю этот вопрос. Спасибо! – user191603
Ответ может непреднамеренно вводить в заблуждение ОП. Этот тип вопроса обычно не предназначен для определения времени выполнения для конкретного значения N, но для любого значения N. Вы, вероятно, были введены в нотацию Big-O (и большой омега и т. Д.). Если это так, ваш учитель ищет нотацию Big-O, которая определяет кривую для алгоритма сортировки оболочки, учитывая все приращения относительно длины ввода (N). Кроме того, ваш учитель хочет получить обобщенный ответ, который работает для любого относительного приращения lim (1). – atk