|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
17.01.2009, 19:57 | #1 |
Регистрация: 16.11.2008
Сообщений: 7
|
Оценка алгоритма
Реализовав алгоритм быстрой сортировки я нахожу время работы алгоритма при определённом количестве элементов в массиве. Мне надо сравнить полученное значение с наихудшей и средней оценкой. Средняя оценка равна O(n*log n), наихудшая O(n*n).
Как связать полученное время с этими формулами? P.S. жду помощи. очень надо. Последний раз редактировалось Алежа; 17.01.2009 в 20:19. |
18.01.2009, 11:25 | #2 |
Пользователь
Регистрация: 17.01.2009
Сообщений: 18
|
Нужно засекать не время, а количество шагов работы алгоритма n.
|
18.01.2009, 12:32 | #3 |
Регистрация: 16.11.2008
Сообщений: 7
|
Не подскажете как это сделать?
|
18.01.2009, 13:39 | #4 |
Пользователь
Регистрация: 17.01.2009
Сообщений: 18
|
Держи код на С
// A - сортируемый массив, a и b - границы, n - оценка сложности (в начале 0)
Код:
Последний раз редактировалось Stilet; 19.01.2009 в 09:01. |
18.01.2009, 13:40 | #5 |
Пользователь
Регистрация: 17.01.2009
Сообщений: 18
|
Извини ошибся не int n, а int *n
|
18.01.2009, 18:34 | #6 |
Регистрация: 16.11.2008
Сообщений: 7
|
Спасибо за это. Но как после нахождения количества шагов сравнивать с теоретической формулой? Как находить константу С из С*n*log n?
|
20.01.2009, 14:18 | #7 |
Пользователь
Регистрация: 17.01.2009
Сообщений: 18
|
Средняя оценка (b-a)*log(b-a)
Наихудшая (b-a)*(b-a) Реальная работа алгоритма n В простейшем случае a=0, b= размер твоего массива - 1 |
20.01.2009, 14:28 | #8 |
Старожил
Регистрация: 13.10.2007
Сообщений: 2,740
|
В книжках написано, что это делается так. Если нужно отсортировать массив по возрастанию, то берут упорядоченный по возрастанию массив и сортируют, это наилучший вариант. Потом это массив инверсируют и снова сортируют, это наихудший вариант. Среднее=(худ - луч)/2. А как считать, по времени или по другим критериям, неважно. Потом сортируют рандомный массив и сравнивают хоть с каким.
P.S. Считать по времени при скорости современных компьютеров нецелесообразно. Массив их 5000 элементов сортируется почти мнгновенно. Лучше по количеству операций сравнения и обмена. Последний раз редактировалось puporev; 20.01.2009 в 14:32. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Сравнительная оценка локальных СУБД | Stilet | Свободное общение | 2 | 23.11.2008 15:33 |
Оценка состояния HDD с помощью системы S.M.A.R.T | scruffy | Общие вопросы Delphi | 0 | 01.05.2008 19:18 |
Изменения алгоритма | delphi_beginner | Общие вопросы Delphi | 2 | 13.05.2007 21:27 |
визуализация алгоритма | Alar | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 30.10.2006 14:10 |