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

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

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

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

@TopLayer · 02.02.2019, 22:46

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\Omega ({n}^{2})\subset \Omega (n)$

@Monny · 02.02.2019, 22:53 **[ТС]**

Все правильно, но по условию я ищу точную нижнюю границу, а вы, если я правильно понял намекаете на нечеткую границу.

@TopLayer · 02.02.2019, 23:03

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

но по условию я ищу точную нижнюю границу

В условии этого нет

@Monny · 02.02.2019, 23:07 **[ТС]**

Ω(n) для четкой, ω(n) для нечеткой, согласно Кормену...

@TopLayer · 02.02.2019, 23:28

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

Ω(n) для четкой, ω(n) для нечеткой, согласно Кормену...

Где вы там такое нашли?

Добавлено через 10 минут
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\Omega (n)=\omega (n)\bigcup \Theta (n)$

@Monny · 02.02.2019, 23:29 **[ТС]**

Фоткид

@TopLayer · 02.02.2019, 23:36

Monny, в первом скрине определение. Подставьте там g(n) = n, f(n)=n^2, c=1, n0=2

Добавлено через 3 минуты
Там говорится, что если функция f(n) = ω(n), то функция g(n)=n не является точной асимптотической оценкой. Про большую омегу такого не сказано - если f(n) = Ω(n), то g(n)=n может как являться точной оценкой, так и не являться.

@Monny · 03.02.2019, 11:05 **[ТС]**

Я согласен с вами, в данном случае она не является точной, так как известна точная граница, которую я и привел (для худшего случая по условию). Возможно я не прав (в который раз перечитал вопрос и в конец запутался), не могли бы вы привезти свой вариант ответа на вопрос... Получается ответ только поиск пары или все приведенные операции?

@TopLayer · 03.02.2019, 12:45

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

Получается ответ только поиск пары или все приведенные операции?

Все операции. Убедитесь, что понимаете:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{2}=\Theta ({n}^{2})$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{2}=\Omega ({n}^{2})$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{2}=\Omega (n)$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{2}\neq \omega ({n}^{2})$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{2}=\omega ({n})$

@Monny · 03.02.2019, 13:31 **[ТС]**

На прикрепленном фото, я правильно проиллюстрировал значения омег и o-функций?
Хмм, согласен со всеми формулами кроме 3, согласно определению:
Ω(n) = { n^2: exist c, n0, такие что 0 <= c*n <= f(n) для всех n >= n0 }
сразу можно заметить, что если подбирать 'с' такое, чтобы g(n) = f(n) нам ничего не мешает сделать так, потому что мы имеем дело с асимптотой, то с->с1*n, т е константа является функцией от n, т е мы фактически сразу видим, что мы написали определение для неточной асимптотической границы, т е для w.
Почему у вас тогда 2 и 4 формулы не равны, фактически это тоже самое...

@TopLayer · 03.02.2019, 15:58

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

Хмм, согласен со всеми формулами кроме 3, согласно определению:
Ω(n) = { n^2: exist c, n0, такие что 0 <= c*n <= f(n) для всех n >= n0 }

Ну, с = 1, n0=2, тогда верно, что 0 <= n <= n^2 для всех n >= 100. Значит n^2 входит в Ω(n).

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

Почему у вас тогда 2 и 4 формулы не равны, фактически это тоже самое...

Маленькая омега (или o) всегда обозначает нечёткую границу, поэтому в четвёртой формуле неравенство.
Большая омега обозначает как функции с чёткой границей, так и с нечёткой.

@Monny · 03.02.2019, 16:50 **[ТС]**

Хмм, у меня впечатление, что вы не читаете, что пишите. Посмотрите определение и покажите мне такую константу ‘c’, что с*n = n^2 при n -> oo. Вы настойчиво описываете w функцию, а мы с вами говорим об Омега большой.

@TopLayer · 03.02.2019, 17:02

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

что с*n = n^2

Где вы в определении равенство увидели?

Добавлено через 49 секунд
Омг, вы похоже не понимаете, что 10 <= 100

@Monny · 03.02.2019, 18:19 **[ТС]**

Признаться честно - это действительно омг, похоже я изначально неправильно понял концепцию этих функций!
Название: Снимок экрана 2019-02-03 в 17.59.48.png
Просмотров: 36

Размер: 9.8 Кб

Название: Снимок экрана 2019-02-03 в 17.59.48.png
Просмотров: 36

Размер: 9.8 Кб

Возьмем ваш пример.
1. ограничена снизу и сверху асимптотой n^2, все правильно: c1*n^2 <= n^2 <= c2*n^2.
2. снизу асимптотой n^2 c1*n^2 <= n^2
3. мы уже нашли асимптотическую границу - это n^2 и n - является просто нижней астматически неточной границей для функции n^2, она включает n^2, но асимтотой не является, т е {exist c1 и n0: c1*n < n^2}.
4. неверно, т к n^2 астматически точная граница, т е может равняться, все верно.
5. снизу ограниченна асимтотически неточночной границей n все верно.
Можете показать, где ошибка? Все согласно определениям.

@TopLayer · 03.02.2019, 18:35

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

Можете показать, где ошибка? Все согласно определениям.

Тут всё верно вроде.

@Monny · 03.02.2019, 19:08 **[ТС]**

... все, что написано в третьей строчке эквивалентно записи n^2 = w(n) =/=Ω(n) .

@TopLayer · 03.02.2019, 19:58

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

... все, что написано в третьей строчке эквивалентно записи n^2 = w(n) =/=Ω(n) .

Ну значит я вас не понял. Я не понимаю, в чём проблема? Определение уже с вами разобрали и выяснили, что n^2=Ω(n).

Добавлено через 43 минуты
Если асимптотика у $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)$ ниже, чем у $https://www.cyberforum.ru/cgi-bin/latex.cgi?g(n)$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)=o(n)$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)=O(n)$ .
Если асимптотика у $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)$ такая же, как и у $https://www.cyberforum.ru/cgi-bin/latex.cgi?g(n)$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)=\theta (n)$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)=O(n)$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)=\Omega(n)$ .
Если асимптотика у $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)$ выше, чем у $https://www.cyberforum.ru/cgi-bin/latex.cgi?g(n)$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)=\omega (n)$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)=\Omega (n)$ .

@Monny · 03.02.2019, 21:26 **[ТС]**

Так а зачем вообще тогда w(g(n)) нужна?

Добавлено через 26 минут
Т е в последней строчке вы говорите, что есть такая функция g(n) и она является асимптотически точной и асимптотически неточной оценкой снизу. Мне кажется или это взаимоисключающие понятия?

@TopLayer · 03.02.2019, 23:21

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

Т е в последней строчке вы говорите, что есть такая функция g(n) и она является асимптотически точной и асимптотически неточной оценкой снизу. Мне кажется или это взаимоисключающие понятия?

Она является только асимптотически неточной оценкой. Маленькая омега для неточной границы, большая - для любой.

Вот у вас есть какое-то своё представление о множестве Ω. Назовите мне две функции f(n) и g(n), для которых верно только одно из двух:
1. f(n) = θ(g(n))
2. f(n) = Ω(g(n))
Грубо говоря, в чём, по-вашему, отличие между θ и Ω?

Добавлено через 3 минуты

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

Так а зачем вообще тогда w(g(n)) нужна?

Чтобы определить множество функций, которые растут быстрее, чем g(n) при неограниченно больших n.

Добавлено через 13 минут

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

, которые растут быстрее

асимптотически

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

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

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

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	02.02.2019, 22:46
	$https://www.cyberforum.ru/cgi-bin/latex.cgi?\Omega ({n}^{2})\subset \Omega (n)$ 1

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	02.02.2019, 22:53 [ТС]
	Все правильно, но по условию я ищу точную нижнюю границу, а вы, если я правильно понял намекаете на нечеткую границу. 0

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	02.02.2019, 23:07 [ТС]
	Ω(n) для четкой, ω(n) для нечеткой, согласно Кормену... 0

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	02.02.2019, 23:29 [ТС]
	Фоткид 0

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	02.02.2019, 23:36
	Monny, в первом скрине определение. Подставьте там g(n) = n, f(n)=n^2, c=1, n0=2 Добавлено через 3 минуты Там говорится, что если функция f(n) = ω(n), то функция g(n)=n не является точной асимптотической оценкой. Про большую омегу такого не сказано - если f(n) = Ω(n), то g(n)=n может как являться точной оценкой, так и не являться. 0

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	03.02.2019, 11:05 [ТС]
	Я согласен с вами, в данном случае она не является точной, так как известна точная граница, которую я и привел (для худшего случая по условию). Возможно я не прав (в который раз перечитал вопрос и в конец запутался), не могли бы вы привезти свой вариант ответа на вопрос... Получается ответ только поиск пары или все приведенные операции? 0

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	03.02.2019, 13:31 [ТС]
	На прикрепленном фото, я правильно проиллюстрировал значения омег и o-функций? Хмм, согласен со всеми формулами кроме 3, согласно определению: Ω(n) = { n^2: exist c, n0, такие что 0 <= cn <= f(n) для всех n >= n0 } сразу можно заметить, что если подбирать 'с' такое, чтобы g(n) = f(n) нам ничего не мешает сделать так, потому что мы имеем дело с асимптотой, то с->с1n, т е константа является функцией от n, т е мы фактически сразу видим, что мы написали определение для неточной асимптотической границы, т е для w. Почему у вас тогда 2 и 4 формулы не равны, фактически это тоже самое... 0

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	03.02.2019, 16:50 [ТС]
	Хмм, у меня впечатление, что вы не читаете, что пишите. Посмотрите определение и покажите мне такую константу ‘c’, что с*n = n^2 при n -> oo. Вы настойчиво описываете w функцию, а мы с вами говорим об Омега большой. 0

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	03.02.2019, 18:19 [ТС]
	Признаться честно - это действительно омг, похоже я изначально неправильно понял концепцию этих функций! Возьмем ваш пример. 1. ограничена снизу и сверху асимптотой n^2, все правильно: c1n^2 <= n^2 <= c2n^2. 2. снизу асимптотой n^2 c1n^2 <= n^2 3. мы уже нашли асимптотическую границу - это n^2 и n - является просто нижней астматически неточной границей для функции n^2, она включает n^2, но асимтотой не является, т е {exist c1 и n0: c1n < n^2}. 4. неверно, т к n^2 астматически точная граница, т е может равняться, все верно. 5. снизу ограниченна асимтотически неточночной границей n все верно. Можете показать, где ошибка? Все согласно определениям. 0

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	03.02.2019, 19:08 [ТС]
	... все, что написано в третьей строчке эквивалентно записи n^2 = w(n) =/=Ω(n) . 0

@Monny 0 / 0 / 0 Регистрация: 01.02.2019 Сообщений: 34
	03.02.2019, 21:26 [ТС]
	Так а зачем вообще тогда w(g(n)) нужна? Добавлено через 26 минут Т е в последней строчке вы говорите, что есть такая функция g(n) и она является асимптотически точной и асимптотически неточной оценкой снизу. Мне кажется или это взаимоисключающие понятия? 0