Асимптотические соотношения для периодических функций

можно ли n^(1 + sin n) записать как O(n^k), где k может быть любым положительным целым числом, большим или равным 2(k>=2)? И определены ли асимптотические обозначения только для возрастающих функций с постоянной скоростью роста или их можно применять к более широкому диапазону, например, к убывающей функции или периодической функции? Больше информации о том же очень приветствуется.


algorithm big-o complexity-theory big-theta asymptotic-complexity
person nerd21    schedule 25.02.2017    source источник
comment
п ^ (1 + грех п) = О (п ^ 2). Другие части вашего вопроса разнообразны, но хорошим местом для начала было бы посмотреть книгу о вычислительной сложности или страницу википедии в big-O, чтобы увидеть, какие виды функций big-O и ему подобные определены.   -  person Paul Hankin    schedule 25.02.2017
comment
@Paul Hankin Я прочитал «Введение в алгоритмы» Томаса Кормена, но не нашел ничего, что развеяло бы мои сомнения. Я спросил своего профессора, но он тоже застрял на том, можем ли мы использовать асимптотическую запись для периодической функции или нет. Так что для меня это до сих пор загадка. Спасибо за ответ:)   -  person nerd21    schedule 25.02.2017
comment
Ответ заключается в том, что вы можете использовать их для любых функций. Например, в википедии формальное определение начинается так: пусть f и g — две функции, определенные на некотором подмножестве действительных чисел. Это не ограничивает f и g дальше этого.   -  person Paul Hankin    schedule 25.02.2017
comment
@PaulHankin Спасибо :)   -  person nerd21    schedule 25.02.2017
comment
Убывающие (положительные) функции всегда равны O(1). Иногда они могут быть даже меньше, например O(1/n).   -  person Paul Hankin    schedule 25.02.2017

Ответы (2)


arrow_upward
1
arrow_downward

Да, вы можете использовать асимптотическую запись для периодических функций, но не для всех.
Максимальное значение sin(x) равно 1, а минимальное значение -1.

Таким образом, мы можем сказать, что существует подмножество натуральных чисел, такое что ограничение f: n -> n(1 + sin n) на него равно O(1)

person Tanuj Yadav    schedule 25.02.2017
comment
Спасибо :) а как насчет уменьшения функций? - person nerd21; 25.02.2017
comment
Возможно, это придирки, но в лучшем/худшем случае, как правило, описываются временные сложности алгоритмов с учетом хороших/плохих входных данных заданного размера n. Здесь есть только функция — ни времени, ни алгоритма. Я предполагаю, что вы имеете в виду что-то вроде того, что существует подмножество натуральных чисел, такое что ограничение f: n → n^(1 + sin n) на него составляет O (1), но обычно это не то, что подразумевается под сложностью в лучшем случае. - person Paul Hankin; 25.02.2017

arrow_upward
0
arrow_downward

Вы можете использовать асимптотическое соотношение для периодических функций. Здесь в вашем вопросе n^(1 + sin n) = O(n^2).
Мы можем использовать f(n)=Θ(g(n)), что означает, что мы можем дать функции как нижнюю, так и верхнюю границу.

f(n)=Θ(g(n)) iff
f(n)<=c1.g(n)
f(n)>=c2.g(n)

где c1 и c2 — некоторые константы.

person Mohit Yadav    schedule 25.02.2017