Сложность операций

@Monny · Регистрация: 01.02.2019

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

Какие из перечисленных операций в худшем случае имеют сложность Ω(n) (т е ограничены снизу) для односвязного списка из n элементов,
задан указатель на первый элемент:
1) поиск минимального - подходит т.к. нам нужно пройти весь список;
2) максимального - подходит т.к. нам нужно пройти весь список;
3) удаление первого элемента равного А - подходит т.к. если он Х стоит в конце (худший случай), то нужно пройти весь список;
4) поиск первой пары повторяющихся элементов - не подходит, т к в худшем случае - это два последних элемента, т е получается, что требуется Ω(n^2) операций;
5) поиск первого элемента не равного Х - подходит, допустим элемент не равный Х стоит в конце, остальные равны Х, т е нужно пройти весь список.
Преподаватель сказал, что я ошибся и я не могу найти где, запрос на помощь...

@Monny · 04.02.2019, 00:39 **[ТС]**

θ ограничивает с двух сторон, а Omega только снизу.
Так что нам мешает это множество определить через Omega тогда? В чем отличие? Я думал в том, что Omega большая - это самая точная оценка на бесконечности, т е функции f(n) и g(n) равны с точностью до константы, а омега малая для случаев, когда нам достаточно знания того факта, что функция будет больше выбранной, которая просто меньше f(n), т е на бесконечности f(n) > g(n).

Добавлено через 3 минуты
И определения согласуются с этой логикой...

@TopLayer · 04.02.2019, 01:23

θ ограничивает с двух сторон, а Omega только снизу.
Вот именно - только снизу. И поэтому n^100500 входит в Ω(n^2).

Сообщение от Monny

Я думал в том, что Omega большая - это самая точная оценка на бесконечности

Самая точная асимптотическая оценка - θ.

Сообщение от Monny

И определения согласуются с этой логикой...

Нет. В определении Ω одно неравенство по сути: f(n) >= с*g(n), т.е. неимоверно быстрорастущая функция f(n) подойдёт. Но также подойдёт и f(n) = g(n) / 100

@Monny · 04.02.2019, 10:50 **[ТС]**

Спасибо, исчерпывающе.
Т е получается, что все ответы правильны? А если бы в условии стояло Ω(n^2), то тогда только 4 ое?

@TopLayer · 04.02.2019, 11:20

Сообщение от Monny

Т е получается, что все ответы правильны? А если бы в условии стояло Ω(n^2), то тогда только 4 ое?

Да.

@Shamil1 · 04.02.2019, 16:06

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

Новые блоги и статьи Все статьи Все блоги /
Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .	Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .
Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34

	Сложность операций 02.02.2019, 11:23. Показов 4901. Ответов 24 Метки односвязанные списки (Все метки) Какие из перечисленных операций в худшем случае имеют сложность Ω(n) (т е ограничены снизу) для односвязного списка из n элементов, задан указатель на первый элемент: 1) поиск минимального - подходит т.к. нам нужно пройти весь список; 2) максимального - подходит т.к. нам нужно пройти весь список; 3) удаление первого элемента равного А - подходит т.к. если он Х стоит в конце (худший случай), то нужно пройти весь список; 4) поиск первой пары повторяющихся элементов - не подходит, т к в худшем случае - это два последних элемента, т е получается, что требуется Ω(n^2) операций; 5) поиск первого элемента не равного Х - подходит, допустим элемент не равный Х стоит в конце, остальные равны Х, т е нужно пройти весь список. Преподаватель сказал, что я ошибся и я не могу найти где, запрос на помощь... 0

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	04.02.2019, 00:39 [ТС]
	θ ограничивает с двух сторон, а Omega только снизу. Так что нам мешает это множество определить через Omega тогда? В чем отличие? Я думал в том, что Omega большая - это самая точная оценка на бесконечности, т е функции f(n) и g(n) равны с точностью до константы, а омега малая для случаев, когда нам достаточно знания того факта, что функция будет больше выбранной, которая просто меньше f(n), т е на бесконечности f(n) > g(n). Добавлено через 3 минуты И определения согласуются с этой логикой... 0

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	04.02.2019, 10:50 [ТС]
	Спасибо, исчерпывающе. Т е получается, что все ответы правильны? А если бы в условии стояло Ω(n^2), то тогда только 4 ое? 0

@Shamil1 Модератор 3140 / 2288 / 469 Регистрация: 26.03.2015 Сообщений: 8,900
	04.02.2019, 16:06
	Не указано ограничение на использование дополнительной памяти. Поиск первой пары повторяющихся элементов можно быстрее выполнить. 2

Опции темы

Сложность операций

Решение