Асимптотический анализ для двух переменных?

11

Как определяется асимптотический анализ (большой o, маленький o, большой тэта, большой тэта и т. Д.) Для функций с несколькими переменными?

Я знаю, что в статье Википедии есть раздел, но он использует много математических обозначений, которые мне незнакомы. Я также нашел следующую статью: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf Однако эта статья очень длинная и содержит полный анализ асимптотического анализа, а не просто определение. Опять же, частое использование математических обозначений усложнило понимание.

Может кто - то дать определение асимптотического анализа без сложных математических обозначений?

ПАВ
источник
1
Сильно связаны: что означает O (m + n)?
Юхо

Ответы:

8

Асимптотическое обозначение для функций с множественными переменными определяется аналогично его единственному переменному аналогу. В одной переменной случае мы говорим , что , если и только если существует константы С , N , что для всех п > N мы имеем п ( п ) C г ( п ) , Другими словами F ( п ) ограничена сверху некоторой кратной г ( п )е(N)О(грамм(N))С,Nn>Nf(n)Cg(n)f(n)g(n)для всех больше некоторого фиксированного N .NN

В многомерном случае определение почти такое же, за исключением того, что у вас есть еще несколько переменных, о которых нужно беспокоиться. Пусть Давайте является функцией двух переменных. Мы хотим занного е сверху другой функции двух переменных. Таким образом , мы говорим , что п ( п , т ) O ( г ( п , т ) ) , если и только если существует константы C , N , что для всех п > N и т > Н мы имеемf(N,м)еf(n,m)O(g(n,m))C,Nn>Nm>N . Определение почти точно так же,исключениемтеперь все наши переменные должны быть большечем нашей фиксированной константой N .f(n,m)Cg(n,m)N

В статье в Википедии использовался для обозначения вектора в R d, что означало бы, что f и g были многопараметрическими функциями от переменных d (т. Е. F , g : R dR ). Говоря , что х я > N для всех I означает , что каждый компонент х должен быть больше , чем N .xRdfgdf,g:RdRxi>NixN

Марк Хури
источник
2
Спасибо! Просто подтверждает, но является ли определение: (1) «для всех n> N и m> N» или (2) «для всех n> N или m> N»? Вы и Wikipedia использовать «и» определение, однако Clrs использует «или» определение.
SAS
1
Это определенно «и».
Марк Хури