0 / 0 / 0
Регистрация: 03.03.2015
Сообщений: 4
|
||||||
1 | ||||||
Количество обменов и сравнений в HeapSort03.03.2015, 23:19. Показов 5132. Ответов 3
Метки нет Все метки)
(
Всем доброго времени суток!
![]() Для удобства отображу это так : Размерность К-сто сравнений К-ство обменов 100----------------34040---------------------924 500----------------857254--------------------23351 1000----------------3429339------------------86187 5000----------------85004946-----------------1989531 Насколько я понял (возможно неправильно ![]() 100: 100*log100 = 200; 924/200=4.62; 34040/200=170.2 500: 500*log500 = 1349.49; 23351/1349.49 = 66.8; 857254/1349.49 = 635.24 Ну вообщем и так далее. Пожалуйста, можете подсказать в чем проблема: возможно я что-то не так понял или счетчики неправильно стоят (хотя я вроде просмотрел, там по идее все правильно), вообщем не знаю я ![]() ![]()
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
|
|
03.03.2015, 23:19 | |
Ответы с готовыми решениями:
3
Сортировка вставками: количество сравнений и обменов Быстрая сортировка: посчитать количество сравнений и обменов
Как теоретически (не программно) посчитать количество сравнений и обменов в пузырьковой сортировке? |
0 / 0 / 0
Регистрация: 03.03.2015
Сообщений: 4
|
|
05.03.2015, 09:41 [ТС] | 2 |
Неужели никто не сможет помочь?
![]()
0
|
![]() ![]() |
|
05.03.2015, 10:31 | 3 |
А тут нечего помогать ибо количество операций зависит от структуры данных. То что результаты у вас не укладываются в теоретические это не удивительно. Теоретическая сложность дает лишь качественные оценки, а не количественные и поэтому проводить подобные сравнения некорректно.
0
|
0 / 0 / 0
Регистрация: 03.03.2015
Сообщений: 4
|
|
05.03.2015, 18:09 [ТС] | 4 |
Вы меня не поняли. Я понимаю, что теоретическая оценка не будет совпадать с экспериментальной, и оцениваю я как раз не количество. Как я понял, вы под структурой данных понимаете экземпляр типа данных, который во всех случаях постоянный. Из этого следует, что соотношение между экспериментальной и теоретической оценкой (для n =500, 1000, ...) должно быть относительно постоянным.
Кликните здесь для просмотра всего текста
43/10 = 4.3 (n=10) 823/200 = 4.115 (n=100) 5274/1350 = 3.9 (n=500) 11538/3000 = 3.9 (n=1000) То есть то, о чем я говорил, все-таки имеет место. В программе, код которой я скинул выше, это выглядит следующим образом: при переходе с n=100 к n=500 отношение меняется с 4.62 до 66.8 (то есть в 14.5 раз увеличивается, и это так и продолжается с увеличением размерности без всякой закономерности), а не на 0.1-0.6 как по идее для этого случая должно быть.
0
|
05.03.2015, 18:09 | |
Помогаю со студенческими работами здесь
4
Подсчет количества обменов и сравнений в алгоритмах сортировки
Для челночной сортировки определить количество сравнений и обменов Как посчитать количество обменов и сравнений при сортировке слиянием? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |