0 / 0 / 0
Регистрация: 03.03.2015
Сообщений: 4
|
||||||
Количество обменов и сравнений в HeapSort03.03.2015, 23:19. Показов 5955. Ответов 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
Сортировка вставками: количество сравнений и обменов Быстрая сортировка: посчитать количество сравнений и обменов
|
![]() ![]() ![]() |
||
05.03.2015, 10:31 | ||
0
|
0 / 0 / 0
Регистрация: 03.03.2015
Сообщений: 4
|
|
05.03.2015, 18:09 [ТС] | |
Вы меня не поняли. Я понимаю, что теоретическая оценка не будет совпадать с экспериментальной, и оцениваю я как раз не количество. Как я понял, вы под структурой данных понимаете экземпляр типа данных, который во всех случаях постоянный. Из этого следует, что соотношение между экспериментальной и теоретической оценкой (для 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
Как теоретически (не программно) посчитать количество сравнений и обменов в пузырьковой сортировке? Подсчет количества обменов и сравнений в алгоритмах сортировки
Для челночной сортировки определить количество сравнений и обменов Как посчитать количество обменов и сравнений при сортировке слиянием? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Опции темы | |
|
Новые блоги и статьи
![]() |
||||
Реализация Domain-Driven Design с Java
Javaican 20.05.2025
DDD — это настоящий спасательный круг для проектов со сложной бизнес-логикой. Подход, предложенный Эриком Эвансом, позволяет создавать элегантные решения, которые точно отражают реальную предметную. . .
|
Возможности и нововведения C# 14
stackOverflow 20.05.2025
Выход версии C# 14, который ожидается вместе с . NET 10, приносит ряд интересных нововведений, действительно упрощающих жизнь разработчиков. Вы уже хотите опробовать эти новшества? Не проблема! Просто. . .
|
Собеседование по Node.js - вопросы и ответы
Reangularity 20.05.2025
Каждому разработчику рано или поздно приходится сталкиватся с техническими собеседованиями - этим стрессовым испытанием, где решается судьба карьерного роста и зарплатных ожиданий. В этой статье я. . .
|
Cython и C (СИ) расширения Python для максимальной производительности
py-thonny 20.05.2025
Python невероятно дружелюбен к начинающим и одновременно мощный для профи. Но стоит лишь заикнуться о высокопроизводительных вычислениях — и энтузиазм быстро улетучивается. Да, Питон медлительнее. . .
|
Безопасное программирование в Java и предотвращение уязвимостей (SQL-инъекции, XSS и др.)
Javaican 19.05.2025
Самые распространёные векторы атак на Java-приложения за последний год выглядят как классический "топ-3 хакерских фаворитов": SQL-инъекции (31%), межсайтовый скриптинг или XSS (28%) и CSRF-атаки. . .
|
Введение в Q# - язык квантовых вычислений от Microsoft
EggHead 19.05.2025
Microsoft вошла в гонку технологических гигантов с собственным языком программирования Q#, специально созданным для разработки квантовых алгоритмов. Но прежде чем погружаться в синтаксические дебри. . .
|
Безопасность Kubernetes с Falco и обнаружение вторжений
Mr. Docker 18.05.2025
Переход организаций к микросервисной архитектуре и контейнерным технологиям сопровождается лавинообразным ростом векторов атак — от тривиальных попыток взлома до многоступенчатых кибератак, способных. . .
|
Аугментация изображений с Python
AI_Generated 18.05.2025
Собрать достаточно большой датасет для обучения нейронной сети — та ещё головная боль. Часами вручную размечать картинки, скармливать их ненасытным алгоритмам и молиться, чтобы модель не сдулась при. . .
|
Исключения в Java: советы, примеры кода и многое другое
Javaican 18.05.2025
Исключения — это объекты, созданные когда программа сталкивается с непредвиденной ситуацией: файл не найден, сетевое соединение разорвано, деление на ноль. . . Список можно продолжать до бесконечности. . . .
|
Как сделать SSO (Single Sign-On) в C# приложении
stackOverflow 18.05.2025
SSO — это механизм, позволяющий пользователю пройти аутентификацию один раз и получить доступ к нескольким приложениям без повторного ввода учетных данных. Вы наверняка сталкивались с ним, когда. . .
|