Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Нахождение констант в ассимптотических обозначениях  [new]
vi0
Member

Откуда:
Сообщений: 120
Коллеги, подскажите пожалуйста по какой логике было принято, что в правом неравенстве n>=1 ?
это из "Алгоритмы. Построение и анализ" Кормена

К сообщению приложен файл. Размер - 140Kb
25 сен 18, 04:08    [21684860]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Потому что делить на 0 нельзя. А отрицательный числа видимо тоже не подошли под неравество.
25 сен 18, 09:12    [21684961]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
vi0
Коллеги, подскажите пожалуйста по какой логике было принято, что в правом неравенстве n>=1 ?
это из "Алгоритмы. Построение и анализ" Кормена

n представляет собой размер входных данных, потому в качестве аргумента рассматриваются положительные числа. Только вопрос вы сформулировали не совсем верно, ничего "принято" не было. Автор лишь показал, что правое неравенство выполняется при для . Если угодно, напишите при n>=100, т.о. n0=100, константы не изменятся.
25 сен 18, 21:21    [21685982]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
vi0
Member

Откуда:
Сообщений: 120
SashaMercury, почему автор использовал именно 1 в решении, а не 100, и почему использовал 7 в решении левого неравенства, а не 100? почему вы не поставили квантор всеобщности перед константой?
26 сен 18, 04:52    [21686145]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
exp98
Member

Откуда:
Сообщений: 1492
vi0,
сравни с определением предела последовательнгости:
для любого эпс существуует n0 такое что для любого N, начиная с n0 выполняется, ....

Здесь похоже:
Существуют константы С1 не больше С2,
для них существует n0 такое что для любого N, начиная с n0 выполняется, ....

Авторы как и лекторы часто опускают то, что полагается известным. Также часто авторы при этом ещё и недостаточно строго выражаются, как в данном случае. Читая, особенно переводные материалы, надо уметь мысленно постоянно верифицировать их промежуточные результаты. К этому следует привыкнуть.
26 сен 18, 14:03    [21686736]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
vi0
SashaMercury, почему автор использовал именно 1 в решении, а не 100, и почему использовал 7 в решении левого неравенства, а не 100? почему вы не поставили квантор всеобщности перед константой?


Автор пишет ниже о том, что мог бы выбрать и другие константы, однако главное, что такой выбор в приницпе существует. Найдите определение того, о чем говорится в книге и внимательно прочитайте и попытайтесь понять, и я думаю, что все станет на свои места.
27 сен 18, 19:51    [21688509]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
vi0
Member

Откуда:
Сообщений: 120
SashaMercury
vi0
SashaMercury, почему автор использовал именно 1 в решении, а не 100, и почему использовал 7 в решении левого неравенства, а не 100? почему вы не поставили квантор всеобщности перед константой?


Автор пишет ниже о том, что мог бы выбрать и другие константы, однако главное, что такой выбор в приницпе существует. Найдите определение того, о чем говорится в книге и внимательно прочитайте и попытайтесь понять, и я думаю, что все станет на свои места.
я не спрашивал про константы. читайте внимательно.
29 сен 18, 07:06    [21689725]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
vi0
Member

Откуда:
Сообщений: 120
exp98
vi0,
сравни с определением предела последовательнгости:
для любого эпс существуует n0 такое что для любого N, начиная с n0 выполняется, ....

Здесь похоже:
Существуют константы С1 не больше С2,
для них существует n0 такое что для любого N, начиная с n0 выполняется, ....

Авторы как и лекторы часто опускают то, что полагается известным. Также часто авторы при этом ещё и недостаточно строго выражаются, как в данном случае. Читая, особенно переводные материалы, надо уметь мысленно постоянно верифицировать их промежуточные результаты. К этому следует привыкнуть.
Спасибо.
29 сен 18, 07:10    [21689726]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
exp98
vi0,

Авторы как и лекторы часто опускают то, что полагается известным. Также часто авторы при этом ещё и недостаточно строго выражаются, как в данном случае. Читая, особенно переводные материалы, надо уметь мысленно постоянно верифицировать их промежуточные результаты. К этому следует привыкнуть.


Естественно, Томас Кормен и компания не могут доступно донести материал до светлых голов :) Вообще говоря, если бы они выражались "достаточно строго", то наверное таких вопросов у тс бы не возникло, потому что до этой страницы он бы вряд-ли дошел
1 окт 18, 20:30    [21691837]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
Мудроглюков
Member

Откуда:
Сообщений: 8313
хе-хе
так если 0<n<1, то при n стремящихся к нулю что получается-то?
2 окт 18, 14:37    [21692715]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
exp98
Member

Откуда:
Сообщений: 1492
Тов. Мудроглюков, не путайте пож чел-ка.
Сбольшой долей вероятности речь идёт о натуральных n. Во всяк "для достаточно больших" как сказано. Так что n стреммится к беск-сти.

SashaMercury, я считаю, что вопрос ТСа был добросовестным, почему бы и не ответить без сарказма. А что некоторые так и родились прямо с этими знаниями? лично я - нет. Тем более на картинке дано определение ассимптотики совсем как дважды два= 7-8, но никак не 10.
3 окт 18, 18:19    [21694430]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
Eugene New
Member

Откуда:
Сообщений: 456
SashaMercury,
Вообще говоря, если бы они выражались "достаточно строго"

Было бы лучше. Все эти "упрощения" только запутывают.

Если бы сначала дали определение, что "для достаточно больших n" означает - "существует такое n0, что для всех n >=n0" у тс вопроса бы не возникло.
А теперь сидят все тут и гадают, что бы это значило.. А каково студентам, которые не знают правильный ответ?
3 окт 18, 20:51    [21694573]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
Мудроглюков
Member

Откуда:
Сообщений: 8313
exp98
Тов. Мудроглюков, не путайте пож чел-ка.
Сбольшой долей вероятности речь идёт о натуральных n. Во всяк "для достаточно больших" как сказано. Так что n стреммится к беск-сти.



это топекстартер путает народ вообще-то
вот еще раз когда перечитал первое сообщение топика, информация из какой темы это сразу всплыло в сознании = это
же из оценок сложности алгоритмов, где так анализируются построенные функции ресурсозатратности-трудоемкости алгоритмов,
где n - это условное количество: каких-то основных объектов на входе алгоритма, каких-то базовых несокращаемых операций
алгоритма, ...,
и естественно n>=1

хе-хе
4 окт 18, 14:31    [21695247]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
vi0
Member

Откуда:
Сообщений: 120
Мудроглюков
это же из оценок сложности алгоритмов, где так анализируются построенные функции ресурсозатратности-трудоемкости алгоритмов,
где n - это условное количество: каких-то основных объектов на входе алгоритма, каких-то базовых несокращаемых операций
алгоритма, ...,
и естественно n>=1 хе-хе

не ясна была логическая цепочка выведений этих констант

например для левого неравенства принято n >=7 (а не 1 как для правого неравенства)
я так понимаю, что это причина в том, что минимальное натуральное число при котором разница будет положительной, т.к. с1 положительное по определению.
отсюда я делаю вывод что не очевидно, что n>=1 в правом неравенстве, из той логики, что это количество обрабатываемых объектов/шагов алгоритма

в общем многое в рассуждениях опускается, как сказал exp98, приводится сжато
поэтому приходится самому додумывать рассуждения
17 окт 18, 13:45    [21706500]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение констант в ассимптотических обозначениях  [new]
exp98
Member

Откуда:
Сообщений: 1492
vi0
...не ясна была логическая цепочка выведений этих констант
...отсюда я делаю вывод что не очевидно, что n>=1 в правом неравенстве, из той логики, что это количество обрабатываемых объектов/шагов алгоритма
Не знаю что там раньше писалось, наверняка речь шла о натуральных числах, след-но n>=1 по определению.
Автор просто рассуждал как решить неравенство. Т.е. подобрать с1 и с2 и n0. Неравенство простое, выражение возрастающее. Автор указал очевидные константы и фсё. Формально говоря это была система 2-х неравенств. Т.о. для подобранных с1 и с2 достаточно взять пересечение множеств n>=1 и n>=7. Вот и вся логика.
По большому счёту так обычно и рассуждают. Для таких простых случаях действительно нафиг делать подробные выкладки.
19 окт 18, 22:28    [21709585]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить