сложность алгоритма - Помощь студентам - Страница 2

NiCola999 · 22.11.2009, 18:00

ну да разложить, чтобы препод понял откуда взялось O(n) , я не разу этим не занимался)

LeBron · 22.11.2009, 18:59

Росписать функцию зависимости количества операций от количества монет сможете? Вот, фактически, что бы доказать формально (это и так очевидно, но преподу "очевидно" не скажеш), что асимптотика именно такая, достаточно просто посмотреть, к чему стремиться эта функция. Найти ее lim в бесконечности.

NiCola999 · 22.11.2009, 19:08

Цитата:

Росписать функцию зависимости количества операций от количества монет сможете?

боюсь нет)) в этом и заключается вопрос данной темы

LeBron · 22.11.2009, 19:15

Ну так попробуйте. Это кажеться в 11 класе учат (не уверен). Количество монет в 1, 5 и 10 копеек не может быть больше определенного числа при любом значении n. Значит, их можно отбросить. А 25копеечных будет n div 25. Так как n/(n div 25) стремиться к 25, то график зависимости будет стремиться к функции y=x*1/25. Надеюсь, Вы согласны, что эта функция линейная?
З.Ы. Ну это с учетом алгоритмической формализации, только по количеству монет. Так как, к примеру, на одно добавление идет 2 операции, то умножаем на 2. Ну и так далее. Но порядок остаеться тем самым.

NiCola999 · 22.11.2009, 19:33

кажется понял) значит теперь мне надо найти предел от ф-ии 2x/25 при x->беск? lim будет бесконечность, тогда сложность получ O(n)(тета от n) ?

22.11.2009, 19:15	#14
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Ну так попробуйте. Это кажеться в 11 класе учат (не уверен). Количество монет в 1, 5 и 10 копеек не может быть больше определенного числа при любом значении n. Значит, их можно отбросить. А 25копеечных будет n div 25. Так как n/(n div 25) стремиться к 25, то график зависимости будет стремиться к функции y=x1/25. Надеюсь, Вы согласны, что эта функция линейная? З.Ы. Ну это с учетом алгоритмической формализации, только по количеству монет. Так как, к примеру, на одно добавление идет 2 операции, то умножаем на 2. Ну и так далее. Но порядок остаеться тем самым. Последний раз редактировалось LeBron; 22.11.2009 в 19:25.*

22.11.2009, 19:33	#15
NiCola999 Не Участник клуба Регистрация: 29.10.2009 Сообщений: 1,456	кажется понял) значит теперь мне надо найти предел от ф-ии 2x/25 при x->беск? lim будет бесконечность, тогда сложность получ O(n)(тета от n) ? Последний раз редактировалось NiCola999; 22.11.2009 в 19:36.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Сложность с запросом БД	k1r1ch	БД в Delphi	4	27.09.2009 18:50
Сложность взлома XLS	Alex Cones	Свободное общение	13	29.08.2009 15:13
Требуется дописать программу на QT. За деньги, сложность низкая.	Static2	Фриланс	4	27.02.2009 14:32
Уже не студент, и не могу преодолеть сложность (строки, *.txt)	SarahConner	Помощь студентам	6	13.01.2009 16:24
Сложность Алгоритма	PChEL@	Помощь студентам	3	26.05.2007 07:56

22.11.2009, 18:00	#11
NiCola999 Не Участник клуба Регистрация: 29.10.2009 Сообщений: 1,456	ну да разложить, чтобы препод понял откуда взялось O(n) , я не разу этим не занимался)

22.11.2009, 18:59	#12
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Росписать функцию зависимости количества операций от количества монет сможете? Вот, фактически, что бы доказать формально (это и так очевидно, но преподу "очевидно" не скажеш), что асимптотика именно такая, достаточно просто посмотреть, к чему стремиться эта функция. Найти ее lim в бесконечности.