worst case алгоритмов сортировки
Здр,
Один из вопросов на который следует найти ответ.
Значит сейчас изучаем различные алгоритмы сортировки, время сортировки и так д...
Может кто знает, или знает как это сделать.
1. Как посчитать worst case?
Например при bubble sort есть определенное число проходов цыкла и определенное число перестановок.
Так вот в bubble sort worst case =n^2 Здесь мне наверное нужно считать проходы цыкла.
В QuickSort worst case = n^2 - так вот собственно е чему я все это. Мне нужно найти такую последовательность элементов чтоб при сортировке Quick sort случился worst case. насколько я понимаю, то нужно считать сколько раз мы поменяли местами элементы?
Припустим у меня 10 элементов, чтоб случился worst case нужно получить 100 в результате, что это за последовательность такая?
Спасибо за ответ.
Один из вопросов на который следует найти ответ.
Значит сейчас изучаем различные алгоритмы сортировки, время сортировки и так д...
Может кто знает, или знает как это сделать.
1. Как посчитать worst case?
Например при bubble sort есть определенное число проходов цыкла и определенное число перестановок.
Так вот в bubble sort worst case =n^2 Здесь мне наверное нужно считать проходы цыкла.
В QuickSort worst case = n^2 - так вот собственно е чему я все это. Мне нужно найти такую последовательность элементов чтоб при сортировке Quick sort случился worst case. насколько я понимаю, то нужно считать сколько раз мы поменяли местами элементы?
Припустим у меня 10 элементов, чтоб случился worst case нужно получить 100 в результате, что это за последовательность такая?
Спасибо за ответ.
И тебе "здр", добрый человек.
[QUOTE=webdev]
Один из вопросов на который следует найти ответ.
[/QUOTE]
Кому следует? :)
[QUOTE=webdev]
Припустим у меня 10 элементов, чтоб случился worst case нужно получить 100 в результате, что это за последовательность такая?
[/QUOTE]
На самом деле, чтобы получить для быстрой сортировкой сложность O(N^2), нужно очень сильно постараться... В большинстве случаев там получается O(n lg n). А квадратичную сложность вы получите, если на каждом шаге сортировки в качестве опорного будет выбираться либо наименьший, либо наибольший элемент последовательности.
[QUOTE=webdev]
Один из вопросов на который следует найти ответ.
[/QUOTE]
Кому следует? :)
[QUOTE=webdev]
Припустим у меня 10 элементов, чтоб случился worst case нужно получить 100 в результате, что это за последовательность такая?
[/QUOTE]
На самом деле, чтобы получить для быстрой сортировкой сложность O(N^2), нужно очень сильно постараться... В большинстве случаев там получается O(n lg n). А квадратичную сложность вы получите, если на каждом шаге сортировки в качестве опорного будет выбираться либо наименьший, либо наибольший элемент последовательности.
:) Ну мне, даже следуя с того, что я его задал. :)
ну я знаю, что получается вот такое в основном O(n lg n) - поэтому задал такой вопрос, так как и представить не могу, что это за последовательность такая. :(
ну я знаю, что получается вот такое в основном O(n lg n) - поэтому задал такой вопрос, так как и представить не могу, что это за последовательность такая. :(
Вот, я ж писал:
[QUOTE=Alexander92]
квадратичную сложность вы получите, если на каждом шаге сортировки в качестве опорного будет выбираться либо наименьший, либо наибольший элемент последовательности
[/QUOTE]
На самом деле, это вопрос даже не только к самой последовательности, а к тому, как выбирать опорный элемент. Последовательность с квадратичной сложностью сходу тоже не придумаю, но если будет интересно - можно посоображать.
[QUOTE=Alexander92]
квадратичную сложность вы получите, если на каждом шаге сортировки в качестве опорного будет выбираться либо наименьший, либо наибольший элемент последовательности
[/QUOTE]
На самом деле, это вопрос даже не только к самой последовательности, а к тому, как выбирать опорный элемент. Последовательность с квадратичной сложностью сходу тоже не придумаю, но если будет интересно - можно посоображать.
Посмотрим, может кто еще отзовется...
Отсортированная последовательность и берем за опорный первый элемент.
