Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 19.01.2010, 20:51
гость

 
Сообщений: n/a

Быстродействие QuickSort
Долго пытаюсь понять быстродействие Quicksort в лучшем, худшем и "среднем" случаях. Где будет Big-O(x), а где Big-Theta(x)??? Я так понимаю, что просто время работы QuickSort для произвольного входа длинны n будет O(n^2), ведь для произвольного входа нельзя гарантировать в качестве верхней границы c(n log n)!? Специалисты по вычислительной сложности, помогите разобраться, plz.
  #2  
Старый 19.01.2010, 21:20
гость

 
Сообщений: n/a

quicksort всегда O(n^2) и Omega(n log n) => лучший случай - Theta(n log n)
мат ожидание рандомизированного quicksort - Theta(n log n)
  #3  
Старый 19.01.2010, 21:33
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
ведь для произвольного входа нельзя гарантировать в качестве верхней границы c(n log n)!?
в обычном quicksort гарантировать нельзя, поэтому и рассматривают мат. ожидание времени работы. То есть иногда, с очень малой вероятностью, может не повезти, но в среднем все замечательно. Доказывается, что мат ожидание времени есть O(n log n), что с учетом нижней границы Omega(n log n) делает его равным Theta(n log n).

Но Theta(n log n) можно и гарантировать 1) есть детерминированный (но малопрактичный) алгоритм нахождения медианы массива за O(n), с ним никакой случайности не нужно, массив будет всегда делиться пополовам, и все будет замечательно, 2) можно комбинировать quicksort и другой гарантированно быстрый алгоритм - если глубина рекурсии превышает clog n (ну или можно еще считать число шагов алгоритм, сравнивать его c c n log n), то переключаться, скажем, на heapsort - такой гибридны алгоритм называется Introsort.
  #4  
Старый 19.01.2010, 21:46
гость

 
Сообщений: n/a

А в целом, по всем алгоритмам, разумно использовать Big-O(x) для обозначения времени работы худшего случая? Т.е. оно может быть и более точно обозначено Big-Theta(x), но использование Big-O не искажает смысла и более подчеркивает, что указывается худшее время работы.

Для обозначения среднего времени работы лучше использовать Big-Theta(x), чтобы подчеркнуть, что оно не только не превышает указанно время, но и не меньше него.

Верно я рассуждаю?
  #5  
Старый 19.01.2010, 21:53
гость

 
Сообщений: n/a

И если взять, к примеру, сортировку пузырьком, которая останавливается, если не сделано ни одного свопа. Какое время работы такого алгоритма? Ведь оно не Big-Theta(n*n), так как может и за линейное время отработать!?
  #6  
Старый 19.01.2010, 22:01
гость

 
Сообщений: n/a

Ну почти везде пишут O(f(n)), даже когда можно было бы использовать и более точное Theta(f(n)). Традиция, типо.

К тому же нижняя граница - она больше интерес представляет для теории. А на практике важнее худший случай, т.е. верхняя оценка. (ну или верхняя оценка мат. ожидания, для рандомизированных алгоритмов)
  #7  
Старый 19.01.2010, 22:06
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
И если взять, к примеру, сортировку пузырьком, которая останавливается, если не сделано ни одного свопа. Какое время работы такого алгоритма? Ведь оно не Big-Theta(n*n), так как может и за линейное время отработать!?
Да, совершенно правильно.

Оценка сложности этого алгоритма на произвольном, фиксированном входе - Omega(n) снизу и O(n^2) сверху.

В среднем однака, если рассматривать вход как случайную перестановку, будет Theta(n^2) - нижняя граница это число инверсий в перестановке, а оно равно n(n-1)/4 = Omega(n^2), ну и сверху O(n^2) => итого Theta(n^2).
  #8  
Старый 19.01.2010, 22:07
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
оно равно n(n-1)/4
мат ожидание равно, в смысле
  #9  
Старый 19.01.2010, 22:23
гость

 
Сообщений: n/a

Спасибо всем за обсуждение. Становится понятно, что аккуратное использование символов не такое уж и простое дело, а везде, по сути, указываются некие "интуитивно-понятные" границы.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
QUICKSORT гость Сортировка и поиск 2 28.11.2009 13:12
QuickSort незарегистрированный Сортировка и поиск 8 18.10.2008 20:37
QuickSort. Выход за пределы массива xmichael Сортировка и поиск 6 02.09.2007 13:33