Определение сложности алгоритма

@Чернышова · Регистрация: 28.10.2019

Author24 — интернет-сервис помощи студентам

Составить блок-схему, составить программу и определить её сложность.
Записать алгоритм сортировки в таблице чисел A[1..n] методом включений. Определить сложность построенного алгоритма.

@ZX Spectrum-128 · 22.11.2019, 16:00

Метод прямого включения

@Cyborg Drone · 28.11.2019, 23:10

Сортировка методом прямого включения, она же сортировка вставками, обладает сложностью алгоритма не хуже O(n²), поскольку в худшем случае, при исходном расположении элементов массива в обратном порядке по отношению к отсортированному расположению элементов, будет произведено примерно n² сравнений / обменов.

Лирическое отступление

Точнее, будет сделано (n-2)(n-1)/2 сравнений и обменов, но в сложности алгоритма указывается асимптотическая зависимость времени работы от n, то есть, не указываются постоянные множители и слагаемые с низким порядком степени. В данном случае: (n-2)(n-1)/2=(n²-3n+2)/2, убираем постоянный множитель 1/2, получим n²-3n+2, убираем то, что по степени меньше 2, получаем n². Если бы у этого n² был бы какой-то множитель, нужно было бы убрать и его.

Конец лирического отступления

Минимальная сложность O(n) будет в том случае, если элементы в массиве уже находятся на нужных местах (будет произведено n-1 сравнение и не будет ни одного обмена).

Средняя сложность этой сортировки (по статистике) составляет O(n²).

Новые блоги и статьи
Как преобразовать список списков в простой список в Python bytestream 22.01.2025 При работе с Python разработчики часто сталкиваются с необходимостью обработки сложных структур данных, среди которых особое место занимают вложенные списки. Эти структуры представляют собой списки,. . .	Что такое GUID / UUID и как их создать bytestream 22.01.2025 В мире разработки программного обеспечения существует постоянная потребность в уникальной идентификации объектов, записей и ресурсов. Эта задача становится особенно актуальной в распределенных. . .	Как добавить пустую директорию в репозиторий Git bytestream 22.01.2025 При работе с системой контроля версий Git разработчики часто сталкиваются с ситуацией, когда необходимо сохранить пустую директорию в репозитории. Данная задача может показаться простой на первый. . .	Как валидировать адрес email в JavaScript bytestream 22.01.2025 JavaScript, как основной язык веб-разработки, предоставляет разработчикам множество инструментов для реализации эффективной валидации email-адресов. От простых встроенных решений до сложных. . .	Как заменить все вхождения подстроки в JavaScript bytestream 22.01.2025 Строки в JavaScript представляют собой неизменяемые последовательности символов, что делает их обработку особенно интересной с точки зрения оптимизации и выбора правильного подхода к решению задач. . . .	Управление версиями пакетов в Node.js. В чем разница между тильдой (~) и кареткой (^) в package.json bytestream 22.01.2025 В современной разработке программного обеспечения управление версиями пакетов играет ключевую роль в обеспечении стабильности и надежности проектов. Node. js, как одна из самых популярных платформ для. . .
Аутентификация на сайте с помощью формы bytestream 21.01.2025 В современном цифровом мире безопасная аутентификация становится краеугольным камнем защиты веб-приложений и пользовательских данных. Каждый день миллионы людей используют различные онлайн-сервисы,. . .	Как получить индекс в цикле for в Python bytestream 21.01.2025 При работе с коллекциями данных в Python часто возникает необходимость не только получить доступ к элементам последовательности, но и знать их позицию в процессе итерации. Индексация в циклах. . .	Как определить адрес, из которого локальный репозиторий Git был клонирован bytestream 21.01.2025 В современной разработке программного обеспечения система контроля версий Git стала неотъемлемой частью рабочего процесса. При работе с Git разработчики часто сталкиваются с необходимостью. . .	Какая разница между операторами == и === в сравнениях в JavaScript bytestream 21.01.2025 В мире веб-разработки JavaScript занимает особое место как динамический язык программирования, предоставляющий разработчикам широкий набор инструментов для создания интерактивных веб-приложений. . . .	Из чего и как собрать свой домашний кинотеатр bt_guru 21.01.2025 Создание домашнего кинотеатра: от идеи до реализации В современном мире домашний кинотеатр стал неотъемлемой частью комфортного жилого пространства, предоставляя возможность наслаждаться. . .	Ошибки стиральных машин bt_guru 21.01.2025 Современные стиральные машины представляют собой сложные электронные устройства, оснащенные множеством датчиков и систем контроля. Они способны самостоятельно определять вес загруженного белья,. . .

@Чернышова 0 / 0 / 0 Регистрация: 28.10.2019 Сообщений: 15
		1
	Определение сложности алгоритма 07.11.2019, 12:19. Показов 1674. Ответов 2 Метки нет (Все метки) Составить блок-схему, составить программу и определить её сложность. Записать алгоритм сортировки в таблице чисел A[1..n] методом включений. Определить сложность построенного алгоритма. 0

@ZX Spectrum-128 6811 / 4568 / 4819 Регистрация: 05.06.2014 Сообщений: 22,438
	22.11.2019, 16:00	2
	Метод прямого включения 1

@Cyborg Drone Модератор 10076 / 5417 / 3356 Регистрация: 17.08.2012 Сообщений: 16,578
	28.11.2019, 23:10	3
	Сортировка методом прямого включения, она же сортировка вставками, обладает сложностью алгоритма не хуже O(n²), поскольку в худшем случае, при исходном расположении элементов массива в обратном порядке по отношению к отсортированному расположению элементов, будет произведено примерно n² сравнений / обменов. Лирическое отступление Точнее, будет сделано (n-2)(n-1)/2 сравнений и обменов, но в сложности алгоритма указывается асимптотическая зависимость времени работы от n, то есть, не указываются постоянные множители и слагаемые с низким порядком степени. В данном случае: (n-2)(n-1)/2=(n²-3n+2)/2, убираем постоянный множитель 1/2, получим n²-3n+2, убираем то, что по степени меньше 2, получаем n². Если бы у этого n² был бы какой-то множитель, нужно было бы убрать и его. Конец лирического отступления Минимальная сложность O(n) будет в том случае, если элементы в массиве уже находятся на нужных местах (будет произведено n-1 сравнение и не будет ни одного обмена). Средняя сложность этой сортировки (по статистике) составляет O(n²). 0

Опции темы