Как определяется асимптотический анализ (большой o, маленький o, большой тэта, большой тэта и т. Д.) Для функций с несколькими переменными?
Я знаю, что в статье Википедии есть раздел, но он использует много математических обозначений, которые мне незнакомы. Я также нашел следующую статью: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf Однако эта статья очень длинная и содержит полный анализ асимптотического анализа, а не просто определение. Опять же, частое использование математических обозначений усложнило понимание.
Может кто - то дать определение асимптотического анализа без сложных математических обозначений?
Ответы:
Асимптотическое обозначение для функций с множественными переменными определяется аналогично его единственному переменному аналогу. В одной переменной случае мы говорим , что , если и только если существует константы С , N , что для всех п > N мы имеем п ( п ) ≤ C г ( п ) , Другими словами F ( п ) ограничена сверху некоторой кратной г ( п )е( n ) ∈ O ( g( н ) ) С, N n>N f(n)≤Cg(n) f(n) g(n) для всех больше некоторого фиксированного N .N N
В многомерном случае определение почти такое же, за исключением того, что у вас есть еще несколько переменных, о которых нужно беспокоиться. Пусть Давайте является функцией двух переменных. Мы хотим занного е сверху другой функции двух переменных. Таким образом , мы говорим , что п ( п , т ) ∈ O ( г ( п , т ) ) , если и только если существует константы C , N , что для всех п > N и т > Н мы имеемf( н , м ) е е(n,m)∈O(g(n,m)) C,N n>N m>N . Определение почти точно так же,исключениемтеперь все наши переменные должны быть большечем нашей фиксированной константой N .f(n,m)≤Cg(n,m) N
В статье в Википедии использовался для обозначения вектора в R d, что означало бы, что f и g были многопараметрическими функциями от переменных d (т. Е. F , g : R d → R ). Говоря , что х я > N для всех I означает , что каждый компонент → х должен быть больше , чем N .x→ Rd f g d f,g:Rd→R xi>N i x→ N
источник