Не понятно, как доказать.

@stdcout · Регистрация: 06.04.2011

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

Во вложении второе задание я не понял. Может ли кто-нибудь объяснить, как вообще осуществляются подобные преобразования, типа (f(n) -> O(f(n))). В книге вроде бы о них ничего не было..
И ещё задания оттуда же.

Известно, что время выполнения одного алгоритма равно O(N * logN), а другого - O(N^3). Что данное выражение неявно говорит об относительной производительности алгоритмов?

Хотел ответить, что это говорит о том, что время выполнения первого алгоритма намного меньше времени выполнения второго при больших N. Но потом вспомнил, что O-нотация показывает верхний предел порядка роста, и поэтому такой вывод сделать нельзя. Т. е. из

C
1
2
f(n) <= c1 * N * logN
g(n) <= c2 * N^3

не следует, что

C
1
f(n) <= g(n)

@Хохол · 10.10.2011, 13:46

Второе задание тоже не понял.

Что касается сравнения асимптотик алгоритмов - действительно, если формально следовать определеню, получается, что эта информация ничего не говорит об относительной производительности.
С другой стороны, на практике, когда говорят, что сложность некоторого алгоритма есть O(f(n)), на самом деле имеют в виду, что либо его сложность в худшем случае, либо в среднем равна Θ(f(n)).

@Mr.X · 11.10.2011, 12:40

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

Во вложении второе задание я не понял. Может ли кто-нибудь объяснить, как вообще осуществляются подобные преобразования, типа (f(n) -> O(f(n))).

Ну, если время t работы алгоритма равно
t = O(f(n)),
то это по определению означает, что существуют такие
C и N, что
t <= C * f(N + n), где n – любое натуральное.

Тогда если
t = f(n), где n – любое натуральное,
то очевидно, что
t <= 1 * f(0 + n),
т.е. t = O(f(n)), где C = 1 и N = 0.
Аналогично из определения следует справедливость и остальных преобразований этого задания.

@stdcout · 11.10.2011, 16:07 **[ТС]**

Mr.X, Меня испугал знак равенства. В данном случае, как я понял, он употребляется в том же значении, что и знак принадлежности множеству?

@taras atavin · 11.10.2011, 16:10

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

Хотел ответить, что это говорит о том, что время выполнения первого алгоритма намного меньше времени выполнения второго при больших N. Но потом вспомнил, что O-нотация показывает верхний предел порядка роста, и поэтому такой вывод сделать нельзя.

Тогда при любом достаточно большом N первый алгоритм в худшем случае работает быстрее, чем второй при том же N и тоже в худшем случае.

@stdcout · 11.10.2011, 16:16 **[ТС]**

и знак следствия -> в выражении наподобие:

cO(f(N)) -> O(f(N))

В данном случае наверное был бы более уместным знак эквивалентности?

Добавлено через 4 минуты
taras atavin, нет. O-нотация показывает лишь верхний предел порядка роста. то есть

O(logN) является подмножеством O(N^3)

так как если f(N) <= c * logN, то f(N) <= c * N^3

@Mr.X · 11.10.2011, 16:23

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

Mr.X, Меня испугал знак равенства. В данном случае, как я понял, он употребляется в том же значении, что и знак принадлежности множеству?

Вообще-то это допустимое обозначение, например в Википедии написано:

Обычно выражение «f является „O“ большим („о“ малым) от g» записывается с помощью равенства f(x) = O(g(x)) (соответственно, f(x) = o(g(x))).
Это обозначение очень удобно, но требует некоторой осторожности при использовании (а потому в наиболее элементарных учебниках его могут избегать). Дело в том, что это не равенство в обычном смысле, а несимметричное отношение.

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	10.10.2011, 13:46
	Второе задание тоже не понял. Что касается сравнения асимптотик алгоритмов - действительно, если формально следовать определеню, получается, что эта информация ничего не говорит об относительной производительности. С другой стороны, на практике, когда говорят, что сложность некоторого алгоритма есть O(f(n)), на самом деле имеют в виду, что либо его сложность в худшем случае, либо в среднем равна Θ(f(n)). 1

@stdcout 53 / 53 / 2 Регистрация: 06.04.2011 Сообщений: 209
	11.10.2011, 16:07 [ТС]
	Mr.X, Меня испугал знак равенства. В данном случае, как я понял, он употребляется в том же значении, что и знак принадлежности множеству? 0