Сравнительный анализ алгоритмов

@Равшан · Регистрация: 05.01.2010

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

Здравствуйте, уважаемые форумчане!

Прошу помощи в решении следующих задач:

Задача 1.
Пусть имеется два алгоритма сортировки последовательности элементов. Первый требует 8n2 шагов, второй – 64n lg n шагов.
Определите значения n для которых на одной и той же вычислительной системы:

Первый алгоритм сортирует последовательность быстрее второго.
Значение n для которого время работы обоих алгоритмов одинаково (допускается приближенное равенство).
Второй алгоритм сортирует последовательность быстрее первого.

Задача 2.
Имеется два алгоритма решения задачи. Время, за которое первый алгоритм позволяет получить результат, оценено как 100 n2, для второго аналогичная оценка выражается как 2n. Для указанных оценок решите проблему первой задачи.

План выполнения работы
1. Выполнить сравнительный анализ времени выполнения нерекурсивных алгоритмов с известными оценками порядка сложности.
2. Выполнить математическую оценку сложности составленного алгоритма.

@turbanoff · 30.03.2012, 09:22

По первой задаче.
http://www.wolframalpha.com/in... +lg%28n%29
Думаю догадаетесь по графику, что где.

Новые блоги и статьи Все статьи Все блоги /
Раскрываем внутренние механики Android с помощью контекста и манифеста mobDevWorks 07.07.2025 Каждый Android-разработчик сталкивается с Context и манифестом буквально в первый день работы. Но много ли мы задумываемся о том, что скрывается за этими обыденными элементами? Я, честно говоря,. . .	API на базе FastAPI с Python за пару минут AI_Generated 07.07.2025 FastAPI - это относительно молодой фреймворк для создания веб-API, который за короткое время заработал бешеную популярность в Python-сообществе. И не зря. Я помню, как впервые запустил приложение на. . .	Основы WebGL. Раскрашивание вершин с помощью VBO 8Observer8 05.07.2025 На русском https:/ / vkvideo. ru/ video-231374465_456239020 На английском https:/ / www. youtube. com/ watch?v=oskqtCrWns0 Исходники примера:	Мониторинг микросервисов с OpenTelemetry в Kubernetes Mr. Docker 04.07.2025 Проблема наблюдаемости (observability) в Kubernetes - это не просто вопрос сбора логов или метрик. Это целый комплекс вызовов, которые возникают из-за самой природы контейнеризации и оркестрации. К. . .	Проблемы с Kotlin и Wasm при создании игры GameUnited 03.07.2025 В современном мире разработки игр выбор технологии - это зачастую балансирование между удобством разработки, переносимостью и производительностью. Когда я решил создать свою первую веб-игру, мой. . .
Создаем микросервисы с Go и Kubernetes golander 02.07.2025 Когда я только начинал с микросервисами, все спорили о том, какой язык юзать. Сейчас Go (или Golang) фактически захватил эту нишу. И вот почему этот язык настолько заходит для этих задач: . . .	C++23, квантовые вычисления и взаимодействие с Q# bytestream 02.07.2025 Я всегда с некоторым скептицизмом относился к громким заявлениям о революциях в IT, но квантовые вычисления - это тот случай, когда революция действительно происходит прямо у нас на глазах. Последние. . .	Вот в чем сила LM. Hrethgir 02.07.2025 как на английском будет “обслуживание“ Слово «обслуживание» на английском языке может переводиться несколькими способами в зависимости от контекста: * Service — самый распространённый. . .	Использование Keycloak со Spring Boot и интеграция Identity Provider Javaican 01.07.2025 Два года назад я получил задачу, которая сначала показалась тривиальной: интегрировать корпоративную аутентификацию в микросервисную архитектуру. На тот момент у нас было семь Spring Boot приложений,. . .	Содержание темы с примерами на WebGL 8Observer8 01.07.2025 Все примеры из книги Мацуды и Ли в песочнице JSFiddle Пример выводит точку красного цвета размером 10 пикселей на WebGL 1. 0 и 2. 0 WebGL 1. 0. Передача координаты точки из главной программы в. . .

@Равшан 2 / 1 / 0 Регистрация: 05.01.2010 Сообщений: 32

	Сравнительный анализ алгоритмов 29.03.2012, 21:43. Показов 2381. Ответов 1 Метки нет (Все метки) Здравствуйте, уважаемые форумчане! Прошу помощи в решении следующих задач: Задача 1. Пусть имеется два алгоритма сортировки последовательности элементов. Первый требует 8n2 шагов, второй – 64n lg n шагов. Определите значения n для которых на одной и той же вычислительной системы: Первый алгоритм сортирует последовательность быстрее второго. Значение n для которого время работы обоих алгоритмов одинаково (допускается приближенное равенство). Второй алгоритм сортирует последовательность быстрее первого. Задача 2. Имеется два алгоритма решения задачи. Время, за которое первый алгоритм позволяет получить результат, оценено как 100 n2, для второго аналогичная оценка выражается как 2n. Для указанных оценок решите проблему первой задачи. План выполнения работы 1. Выполнить сравнительный анализ времени выполнения нерекурсивных алгоритмов с известными оценками порядка сложности. 2. Выполнить математическую оценку сложности составленного алгоритма. 0

@turbanoff 4094 / 3828 / 745 Регистрация: 18.05.2010 Сообщений: 9,331 Записей в блоге: 11
	30.03.2012, 09:22
	По первой задаче. http://www.wolframalpha.com/in... +lg%28n%29 Думаю догадаетесь по графику, что где. 0

Опции темы